Лекция Логическая равносильность
Download 429.31 Kb. Pdf ko'rish
|
Лекция 4 Логическая равносильность
- Bu sahifa navigatsiya:
- Признак равносильности формул
- Примеры равносильных формул
|
Лекция 4. Логическая равносильность
Определение 1. Формулы 1 2
, ,...,
) n F X X X и
1 2 ( , ,...,
) n H X X X алгебры высказываний называются равносильными (эквивалентными), если при любых значениях входящих в них пропозициональных переменных логические значения получающихся из формул F и Н высказываний совпадают. Для указания равносильности формул используют обозначение F H . Определение равносильных формул можно записать символически:
1 2 1 2 ( ( , ,..., )) ( , ,..., ))
n F H F A A A H A A A (1)
для любых конкретных высказываний A 1 ,A 2 ,…,A n .
Обе формулы F и Н непременно входят один и те же переменные. Некоторые из переменных X 1 ,X 2 ,…,X n могут фактически отсутствовать в любой из них. Проверим, например, равносильность формул
1 ,
2 ,…,
n . Для этого составим таблицы истинности обеих формул и убедимся, что значения истинности получающихся из них высказываний одинаковы для любых одинаковых наборов значений пропозициональных переменных Х 1 и
Х 2 . (X 1 )
2 )
2
1 )
2
1 )) 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 0 1 0 Проверьте самостоятельно справедливость равносильностей
X 1
1
2
2 , X 1
1
2
2 .
Выписывание в предыдущем определении в формуле F и Н одних и тех же пропорциональных переменных обусловлено стремлением сделать записи и рассуждения более краткими и лаконичными.
выявлении связи между понятием равносильности форму и понятием тавтологии.
Теорема 2 (признак равносильности формул). Две формулы F и Н алгебры высказываний равносильны тогда и только тогда, когда формула F H является тавтологией
╞ F
(2)
Доказательство. Если
то, по
определению 1 1 1 ( ( ,..., )) (
)) n n F A A H A A для любых высказываний A 1 ,…,A n . Тогда, по определению 5 операции эквивалентности 1 1 ( ( ,..., )) ( ( ,..., )) 1
n n F A A H A A , откуда на
основании соотношения (5) заключаем: 1 1 ( ( ,..., )) ( ( ,..., )) 1 n n F A A H A A для любых A 1 ,…,A n . Последнее означает по определению тавтологии, что ╞
Обратными рассуждениями доказывается утверждение: если ╞
Отметим, что выражение F H не является формулой алгебры высказываний. Оно – утверждение о некотором взаимоотношении между формулами F и Н. В приводимом нижнее следствии из теоремы 2 устанавливаются некоторые свойства этого отношения между формулами алгебры высказываний.
Следствие 3. Отношение равносильности между формулами алгебры высказываний:
а) рефлексивно: F F ; б) симметрично: если 1 2
F , то 2 1
F ; в) транзитивно: если 1 2
F и 2 3
F , то 1 3
F , то есть отношение равносильности является отношения эквивалентности.
Доказательство. Рефлексивность следует
непосредственно из
тавтологии теоремы 3 и теоремы 2.
Для доказательства симметричности отношения предположим, что 1 2
F , то есть на основании признака равносильности ╞ F 1
2 . Тогда по тавтологии теоремы 3 заключаем: формула F
1 , принимает всегда те же самые значения, что и формула F
2 , то есть только истинные значения. Следовательно, ╞
2
1 , или, по признаку равносильности, 2 1
F . Симметричность, доказана.
Наконец, если 1 2
F и 2 3
F , то есть ╞ F 1
2 и ╞
2
3 , то на основании определения конъюнкции заключаем: ╞
1
2 )
(F 2
3 ). Привлекая теперь тавтологию из теоремы 3, и правило заключения для получения тавтологий, получаем ╞
1
3 , или (по теореме 2) 1 3
F . Следовательно, отношение транзитивно. Таким образом, - отношение эквивалентности, что и требовалось доказать.
Как и всякое отношение эквивалентности, отношение определяет разбиение множества, на котором оно задано, на непересекающиеся классы эквивалентных элементов. В данном случае множество всех формул алгебры высказываний распадаются на попарно непересекающиеся классы, в каждом из которых находятся равносильные между собой формулы. Один класс, например, образуют все тавтологии, другой – все тождественно ложные формулы, имеется и много других классов.
некоторые основные равносильности. Они получаются, исходя из тавтологий, приведенных в теоремах на основании признаки равносильности формул.
Теорема 4. Справедливы следующие равносильности:
а)
Р
б) P
в) P Q
г) P (Q
д) (P
е) P P
ж) P
з) P
и) P Q
к) P (Q
л) P (Q
м) P (Q
н) P
о) P
п) P
р) (P
с)
(P
т) P Q
у) P
ф) P
х) P Q
ц) P Q
ч) P Q
ш) P
щ) P
з) P
Download 429.31 Kb. Do'stlaringiz bilan baham: 
|