Формулы логики высказываний. Равносильность формул. Равносильные преобразования и упрощения формул

Контрольные вопросы

1. Дайте определение формулы алгебры высказываний. Какие элементы может содержать формула?

2. Какими способами можно упростить запись формулы?

3. Каков приоритет действий основных логических операций?

4. Дайте определение логической возможности формулы.

5. Что такое таблица истинности? Сформулируйте алгоритм построения таблицы истинности.

6. Дайте определение тавтологии и противоречия.

7. Какие формулы называются опровержимыми, выполнимыми?

8. Какие формулы называются равносильными?

9. Какие основные равносильности вам известны?

10. Каким образом можно установить равносильность формул?

11. Сформулируйте правило подстановки.

12. Сформулируйте правило замены.

13. На чем основаны равносильные преобразования формул?

14. Какими способами можно доказать равносильность формул алгебры логик с использованием равносильных преобразований?

Упражнения

11. Учитывая соглашения об упрощении записи формул, упростить запись следующих формул:

1. ;

2. ;

3. .

12. Построить таблицы истинности для следующих формул:

1. ;

2. ;

3. .

13. Докажите основные равносильности логики высказываний с помощью таблиц истинности.

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

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. .

15. Учитывая соглашения об упрощении записи формул, упростит следующие формулы, опустив лишние скобки и знак конъюнкции:

1. ;

2. ;

3. ;

16. Восстановить скобки и знак конъюнкции в формулах, определите порядок действий:

1. ;

2. ;

3. ;

4. ;

5. .

17. Построить таблицы истинности для следующих формул:

    ;	;
    ;	;
    ;	.

18. Упростить выражения, используя законы склеивания или поглощения:

    1. ;

    2. ;

    3. ;

    4. ;

    5. ;

    6. ;

    7. .

19. Используя равносильные преобразования, доказать равносильность формул А и В:

1. ,

2. ,

3. ,

20. Применяя равносильные преобразования доказать тождественную истинность формулы

1. ;

2. .

21. Используя равносильные преобразования, доказать равносильность формул

Булевы функции. Равенство булевых функций. Существенные и фиктивные переменные. Двойственность булевых функций

Контрольные вопросы

1. Дайте определение булевой функции. По какой формуле можно определить количество булевых функций от n переменных

2. Какие существуют способы задания булевых функций?

3. Перечислите основные булевы функции одной и двух переменных.

4. Дайте определение существенных и фиктивных переменных. Какие булевы функции называются равными?

5. Каким образом можно сравнить булевы функции с разным количеством аргументов?

6. Дайте определение функции, двойственной к данной. Сформулируйте закон двойственности и принцип двойственности.

7. Как построить функцию, двойственную к булевой функции.

Упражнения

22. Какая из приведенных записей не является вектором значений булевой функции: , , , . Поясните ответ.

23. Функции заданы с помощью вектора значений. Восстановите таблицы истинности функций:

1. ;

2. .

24. Функция заданна вектором значений . Определить количество переменных функции и указать фиктивные переменные

25. Найти функции, двойственные к данным:

1. ;

2. .

26. Примените закон двойственности к следующим тождествам:

1. ;

2. .

27. Задана булева функция . Записать вектор значений функции.

28. Функция заданна вектором значений . Определить количество переменных функции, указать существенные и фиктивные переменные.

29. Дана функция . Найти .

30. Функция задана с помощью вектора значений. Восстановите таблицу истинности функции.

31. Функция заданна вектором значений. Определить количество переменных функции и указать фиктивные переменные f = (0,0,1,1,1,1,0,0).

32. Найти все фиктивные переменные для следующих функций:

1. ;

2. 

33. Найти функции, двойственные к данным:

2. 

3.