Операция антиэквиваленции

Х У C Å U
Л Л Л
Л И И
И Л И
И И Л

 

Пример 1: составить таблицу истинности для выражения (P®Q) & P

Формула содержит 2 переменные – P и Q, следовательно, в таблице истинности (табл. 1.8.) буде 22 = 4 строки. Расставим приоритеты операций: первое действие – импликация, второе действие – конъюнкция.

Таблица 1.8.

P Q P®Q (P®Q) &P
Л Л И Л
Л И И Л
И Л Л Л
И И И И

 

Пример 2: составить таблицу истинности для выражения

((A®ù B) & C)«((ù (A&B)&C)

Формула содержит 3 переменные – A, В, С, следовательно, в таблице истинности (табл. 1.8.) буде 23 = 8 строк. Расставим приоритеты операций:

Таблица 1.9.

А В С ù B A®ù B (A®ù B) & C A&B ù (A&B) ù (A&B)&C ((A®ù B) & C) «((ù (A&B)&C)
Приоритеты операций 1 2 3 4 5 6 7
Л Л Л И И Л Л И Л И
Л Л И И И И Л И И И
Л И Л Л И Л Л И Л И
Л И И Л И И Л И И И
И Л Л И И Л Л И Л И
И Л И И И И Л И И И
И И Л Л Л Л И Л Л И
И И И Л Л Л И Л Л И

1.3. Равносильность формул.

Пусть имеются две формулы: А (x1, …, хn) и B (x1, …, xn). Формулы называются равносильными, если они принимают одни и те же значение на всех наборах значений переменных х1, …, хп. Другими словами, формулы равносильны, если результирующие значения их таблиц истинности совпадают.

Факт равносильности обозначают «eq».

Важнейшие равносильности алгебры логики можно разбить на три группы.

Основные формулы равносильности:

1. CÚЛeqX

2. XÚИeq И

3. XeqX

4. CeqЛ

5. CCeqЛ -закон противоречия

6. CÚùCeqИ –закон исключенного третьего

7.

законы идемпотентности
XÚXÚ … ÚXeqX

8. C&C& ... &CeqX

9. ùùCeq Х -закон снятия двойного отрицания

10.

законы поглощения
Х &(CÚY)eq Х

11. Х Ú(C&U)eq Х

Формулы равносильности, выражающие одни логические операции через другие:

12. C®UeqùCÚY

13. C®Ueqù(CU)

14. C«Ueq(C®U)&(U®C)

15. C«UeqCU)V(X&Y)

16. C«U eqCÚU)&(CÚùU)

17. ù(CÚY)eqùCU

18.

Законы де Моргана
ù(ùCÚùU)eqXÚY

19. ù(C&U)eqùCÚùU

20. ù(ùCU)eqXÚY

Формулы равносильности, выражающие основные законы алгебры логики:

21. CÚYeqYÚXкоммутативность дизъюнкции;

22. C&UeqU&C -коммутативность дизъюнкции;

23. (XÚY)ÚZ eq XÚ(YÚZ)eqXÚYÚZассоциативность дизъюнкции;

24. (X&Y)&Z eq X&(Y&Z)eqX&Y&Zассоциативность конъюнкции;

25. C& (UÚZ)eq(X&Y)Ú(X&Z) -дистрибутивность конъюнкции относительно дизъюнкции;

26. XÚ(Y&Z) eq (XÚY)&(XÚZ) - дистрибутивность дизъюнкции относительно конъюнкции;

Используя формулы равносильных преобразований 1-26, часть формулы или всю формулу можно заменить равносильной ей формулой. Такие преобразования называются равносильными.

Пример 3: доказать равносильность формул

Х→(X & ù(YÚZ)) (1)

ùX Ú (ùY & ùZ) (2)

составив таблицы истинности для них, а также проведя равносильные преобразования.

Поскольку в каждой формуле содержится 3 переменных, строк в таблицах истинности для каждой формулы будет 23=8. Составим таблицы истинности для обеих формул (табл. 1.10, 1.11):


Таблица 1.10

Таблица истинности для формулы (1)

X Y Z YÚZ ù(YÚZ) X & ù(YÚZ) Х→(X & ù(YÚZ))
Л Л Л Л И Л И
Л Л И И Л Л И
Л И Л И Л Л И
Л И И И Л Л И
И Л Л Л И И И
И Л И И Л Л Л
И И Л И Л Л Л
И И И И Л Л Л

Таблица 1.11

Таблица истинности для формулы (2)

X Y Z ùX ùY ùZ ùY & ùZ ùX Ú (ùY & ùZ)
Л Л Л И И И И И
Л Л И И И Л Л И
Л И Л И Л И Л И
Л И И И Л Л Л И
И Л Л Л И И И И
И Л И Л И Л Л Л
И И Л Л Л И Л Л
И И И Л Л Л Л Л

Из таблиц истинности формул 1.10, 1.11 видно, что истинностные значения формул, находящихся в результирующих столбцах каждой из таблиц, совпадают.

Теперь докажем равносильность этих двух формул, используя равносильные преобразования (в этом примере в скобках указан номер формулы равносильности, на основании которой проведено преобразование)

Х→(X & ù(YÚZ)) eq (17) Х→(X & (ùY&ùZ)) eq (12)

ùXÚ(X & (ùY&ùZ))eq (26) (ùXÚX) & (ùXÚ(ùY&ùZ)) eq(6)

И & (ùXÚ(ùY&ùZ)) eq (3) (ùXÚ(ùY&ùZ))

1.4. Закон двойственности

Операции конъюнкции является двойственной по отношению к операции дизъюнкции, а операции дизъюнкции – двойственна по отношению к операции конъюнкции.

Если А(х1, …, хп) - некоторая формула алгебры логики, то формула, полученная из нее заменой всех операций двойственными им, называется двойственной формулой для А и обозначается А*1, …,хп).

Например, для формулы Аº(х Úy)& z двойственной будет формула

А*º(х & y) Ú z

Преобразования двойственности являются обратимыми, т.е.

*)*

Утверждение1: Любая операции может быть представлена через дизъюнкцию, конъюнкцию и отрицание.

Утверждение2: Если для записи некоторой формулы алгебры логики А используются только знаки операции отрицания, конъюнкции и дизъюнкции, то отрицание такой формулы равносильно двойственной формуле от отрицания всех входящих в нее переменных.

ùА(х1, …, хп) eq А*(ù х1, …, ùхп)

А(х1, …, хп) eq ùА*(ù х1, …, ùхп)

Утверждение равносильности: если две формулы равносильны, то равносильны и двойственные им:

AeqB « (A*eqB*)

A*eqB*)« AeqB

1.5. Тавтологии, противоречия и выполнимые формулы.

Формула, которая принимает значение истина при любых наборах входящих в нее переменных, называется тавтологией(тождественно истинной, общезначимой).

Для указания на тавтологию используют знак «. Например:

D(P®Q)&(Q®R)&P®R

Формула, которая принимает значение «ложь» при любых наборах значений входящих в нее переменных, называется противоречием(тождественно ложной).

Формула, принимающая значение «истина» на одних наборах переменных и значение «ложь» на других, называется выполнимой.

Различные формулы, полученные подстановками других формул в тавтологию, не зависимо от их конкретного содействия, всегда являются истинными в силу одной только своей структуры. Иначе говоря, тавтологии можно рассматривать как некоторые логически-истинные схемы рассуждений или доказательств. Поэтому тавтологии играют роль законов в логике высказываний и претендуют на установление методов постановления правильных умозаключений. Существует бесконечное множество тавтологий, а, значит, и законов логики высказываний. В классической логике наиболее часто используются следующие законы:


<== предыдущая лекция | следующая лекция ==>
Формулы алгебры-логики | Закон тождества ᅣP®P




Дата добавления: 2019-10-16; просмотров: 140; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию, введите в поисковое поле ключевые слова и изучайте нужную вам информацию.

Поделитесь с друзьями:

Если вам понравился данный ресурс вы можете рассказать о нем друзьям. Сделать это можно через соц. кнопки выше.
helpiks.org - Хелпикс.Орг - 2014-2020 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.037 сек.