Математическая логика

Следование, эквивалентность и преобразование формул

жүктеу/скачать 0.93 Mb. бет 3/18 Дата 19.04.2023 өлшемі 0.93 Mb. #472456 түрі Задача

Бұл бет үшін навигация:

• Теорема 2.3. Если A

2. Следование, эквивалентность и преобразование формул Введем на множестве M отношения следования и эквивалентности. Формула B следует из формулы A (обозначается A B), если она истинна на всех наборах высказывательных переменных, на которых истинна формула A. Формула A эквивалентна формуле B (обозначается A  B), если они следуют друг из друга, то есть A B и B A. Легко показать, что это определение эквивалентно определению, введенному в п.1. Теорема 2.1. Формула B следует из формулы A тогда и только тогда, когда тождественно истинна формула A B. Теорема 2.2. Формула A эквивалентна формуле B тогда и только тогда, когда тождественно истинна формула A~B. Эквивалентность формул является отношением эквивалентности, поэтому множество M можно разбить на классы эквивалентности, включив в один класс эквивалентные между собой формулы. Каждой формуле U соответствует класс эквивалентности, который обозначается [U]. Теорема 2.3. Если A есть некоторая подформула формулы U и A эквивалентна формуле B, то формула, полученная заменой A в формуле U на B, эквивалентна U. Иными словами, если A  B, то U(A)  U(B). Например, так как AB  , то (AB)C  ( )C. Следствие. Если U~A и V~B, то: 1) U V  A B; 2) U V  A B; 3) U V  A B; 4) (U~V)  (A~B); 5) U  A. Теорема 2.3 и ее следствие позволяют преобразовывать формулы, упрощая их, и доказывать эквивалентность формул. Приведем список основных тавтологий, выражающих свойства логических операций. Коммутативность: X Y  Y X, X Y  YX. 2. Ассоциативность: (X Y)Z  X (YZ), (XY)Z  X(YZ). 3. Идемпотентность: XX  X, XX  X. Законы поглощения: X(X Y)  X, X (XY)  X. 5. Взаимная дистрибутивность конъюнкции и дизъюнкции: X (YZ)  (X Y)(X Z), X (YZ)  (XY)(XZ). 6. Свойства констант: X0  Л, X1  X, X0  X, X1  1. 7. Законы де Моргана: , . 8. Инволютивность: . 9. Закон противоречия:  0. 10. Закон исключенного третьего:  1. Тождественная истинность всех формул (кроме законов поглощения) уже доказана непосредственно построением таблиц истинности. Задание. Доказать 1-й из законов поглощения. Решение. . Приведем еще несколько эквивалентностей, имеющих широкое применение. . . Склеивание: , . Формула называется приведенной, если она содержит операции конъюнкции, дизъюнкции и операцию отрицания, относящуюся к высказывательным переменным. жүктеу/скачать 0.93 Mb. Достарыңызбен бөлісу: