Задание 5. Для графа построить, если это возможно, его уклад­ку на плоскости

Для графа построить, если это возможно, его уклад­ку на плоскости.

Варианты

1.

2.

3.

4.

6. 7.

8. 9.

10. 11.

12. 13.

14. 15.

16. 17.

18. 19.

20.

5. ОПЕРАЦИИ НАД ВЫСКАЗЫВАНИЯМИ

И ИХ СВОЙСТВА

Теоретические сведения

Под высказыванием понимают предложение, относительно которого имеет смысл утверждать, истинно оно (обозначают символами 1 или И) или ложно (символы 0 или Л). Значения И и Л (или 1 и 0) называются истинностными значениями высказывания, множество {И, Л} (или {0,1}) называют множеством истинностных значений. Заметим, что значение высказывания ситуативно, при этом в каждой ситуации высказывание принимает одно и только одно из двух значений – И или Л.

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

Пусть X и Y – два высказывания. Определим основные логические операции.

Отрицанием высказывания X называют высказывание , которое истинно тогда и только тогда, когда Х ложно. В разговорной речи высказывание соответствует составлению из высказывания Х нового высказывания «не Х» или «неверно, что Х».

Конъюнкцией двух высказываний Х и Y называют высказывание , которое истинно тогда и только тогда, когда истинны оба высказывания. Конъюнкция иначе называется логическим умножением, а Х и Y – сомножителями. В разговорной речи конъюнкция соответствует соединительному союзу «и», – читается как «Х и Y».

Дизъюнкцией двух высказываний Х и Y называют высказывание , которое ложно тогда и только тогда, когда Х и Y ложны. Дизъюнкция иначе называется логическим сложением, а Х и Y – слагаемыми. В разговорной речи дизъюнкция соответствует соединительному союзу «или», – читается как «Х или Y».

Импликацией двух высказываний называют высказывание, которое ложно тогда и только тогда, когда Х – истинно, а Y – ложно. В разговорной речи импликация высказываний соответствует составлению высказывания вида: «Х имплицирует Y», «из Х следует Y», «если Х, то Y», «Х достаточно для Y», «Х только тогда, когда Y», «Y необходимо для Х», «Y тогда, когда Х». В обозначении : Х – посылка, Y – заключение.

Эквиваленцией двух высказываний Х и Y называют высказывание , которое истинно тогда и только тогда, когда истинностные значения высказываний Х и Y совпадают. В разговорной речи эквиваленция двух высказываний соответствует составлению нового высказывания вида «Х эквивалентно Y», «Х тогда и только тогда, когда Y», «Х необходимо и достаточно для Y».

Всякое сложное высказывание, составленное из некоторых исходных высказываний посредством применения логических операций , будем называть формулой алгебры высказываний. Исходные высказывания при этом могут быть постоянными, то есть иметь определенное значение И или Л, или могут не иметь определенного значения. В первом случае исходные высказывания будем называть постоянными элементарными высказываниями, во втором – переменными элементарными высказываниями. Переменные элементарные высказывания будем обозначать заглавными буквами латинского алфавита.

При вычислении по формуле учитывают приоритет операций

,

где знак обозначает убывание приоритета. При необходимости изменить естественную последовательность действий используют скобки.

Символы, соответствующие переменным элементарным высказываниям, называются пропозициональными переменными.

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

1) каждая пропозициональная переменная есть ПФ;

2) если Х и Y – ПФ, то , , , ,

– тоже ПФ.

Иногда понятие формулы расширяют за счет введения в них следующих логических операций:

1. Операция сложения по модулю два .
2. Штрих Шеффера (функция Шеффера) .
3. Функция Вебба (стрелка Пирса) .

Заметим, что каждая пропозициональная переменная принимает значения 0 или 1, тогда ПФ в соответствии с определением логических операций также принимает значения 0 или 1, поэтому ее можно рассматривать как функцию, область значений и область определения которой совпадают и равны {0,1}. Такую функцию будем называть двоичной или булевой функцией.

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

Если функция зависит от n переменных, то таблица истинности содержит 2ⁿ наборов значений переменных.

С помощью таблицы истинности определяют все логические операции над высказываниями:

X	Y

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

ПФ называют тождественно ложной или противоречием, если она принимает значение 0 на всех наборах значений переменных.

ПФ называют выполнимой, если на некоторых наборах значений переменных она принимает значение 1, а на остальных – 0.

Тип ПФ можно определить с помощью таблицы истинности.

Две формулы алгебры высказываний и называются равносильными, если их таблицы истинности совпадают. Равносильность формул будем обозначать через .

Для любых формул X, Y, Z справедливы следующие равносильности:

1. , (коммутативность);

2. , (ассоциативность);

3. , (дистрибутивность);

4. , (идемпотентность);

5. , (законы поглощения );

6. (закон двойного отрицания);

7. , (законы де Моргана);

8. , , , , , (законы, определяющие действия с константами);

9. , (исключение импликации и эквиваленции);

10. (исключение дизъюнкции);

11. (исключение конъюнкции);

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

Примеры решения задач

Задача 1. Упростить ПФ , используя равносильные преобразования.

Решение.

1) Применим дистрибутивный закон, получим

.

2) Так как , то получим

3) По дистрибутивному закону

4) Так как , , то получим

.

Таким образом,

Замечание. Шаги 1-2 в решении можно заменить одним шагом, если использовать закон поглощения

.

Задача 2. Составить таблицу истинности ПФ и определить тип ПФ

Решение. Составим таблицу истинности ПФ

X	Y	Z

Как видно из таблицы истинности, данная ПФ является выполнимой.

Задание 6

Упростить ПФ, используя равносильные преобразования.

Варианты

1. .

2. .

3. .

4. .

5. .

6. .

7. .

8. .

9. .

10. .

11. .

12. .

13. .

14. .

15. .

16. .

17. .

18. .

19. .

20. .

Задание 7

Составить таблицу истинности ПФ и определить тип ПФ.

Варианты

		)
		)

6. НОРМАЛЬНЫЕ И СОВЕРШЕННЫЕ

НОРМАЛЬНЫЕ ФОРМЫ

Теоретические сведения

Определим некоторые канонические представления ПФ.

ПФ называется элементарной конъюнкцией (дизъюнкцией), если она является конъюнкцией (дизъюнкцией) переменных и отрицаний переменных.

Пример.

- элементарная конъюнкция.

- элементарная дизъюнкция.

Говорят, что ПФ задана в дизъюнктивной нормальной форме (ДНФ), если она является дизъюнкцией элементарных конъюнкций.

Пример. - ДНФ.

Говорят, что ПФ задана в конъюнктивной нормальной форме (КНФ), если она является конъюнкцией элементарных дизъюнкций.

Пример. - КНФ.

На основе равносильных преобразований любая формула может быть приведена к нормальной форме (ДНФ или КНФ).

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