![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Теорема 3.1. Дві формули F і Н алгебри висловлень рівносильні тоді й тільки тоді, коли формула є тавтологією, тобто
╞
.
Доведення даної теореми безпосередньо випливає із означення рівносильності формул та означення тавтології.
Зазначимо, що рівносильність формул не є формулою. Це відношення між формулами F і Н логіки висловлень.
Наслідок. Відношення рівносильності між формулами алгебри висловлень
а) рефлексивне: ;
б) симетричне: якщо , то
;
в) транзитивне: якщо і
, то
,
тобто відношення рівносильності між формулами алгебри висловлень є відношенням еквівалентності.
Отже, відношення рівносильності розбиває множину всіх формул алгебри висловлень на класи еквівалентності, які попарно не перетинаються. Один клас, наприклад, утворюють усі тавтології, інший - усі тотожно хибні формули і т. д.
Приклади рівносильних формул. Наведені нижче рівносильності випливають із тавтологій, розглянутих у попередній лекції, на основі ознаки рівносильності.
Теорема 3.2. Мають місце наступні рівносильності:
а) ;
б) ;
в) ;
г) ;
д) ;
ж) ;
з) ;
і) ;
й) ;
к) ;
л) ;
м) ;
н) ;
о) ;
п) (1-й закон де Моргана);
р) (2-й закон де Моргана);
с) ;
т) ;
у) ;
ф) ;
х) ;
ц) ;
ч) ;
ш) ;
щ) .
Дата публикования: 2015-03-26; Прочитано: 334 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!