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

Х У 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. X&ИeqX

4. C&ЛeqЛ

5. C&ùCeqЛ -закон противоречия

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ù(C&ùU)

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

15. C«Ueq(ùC&ùU)V(X&Y)

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

17. ù(CÚY)eqùC&ùU

18.

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

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

20. ù(ùC&ùU)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». Например:

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

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

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

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


1234567




Дата добавления: 2019-10-16; просмотров: 677;

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

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

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

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.02 сек.