2. Правило записи скнф функции по таблице истинности:
Для всех наборов переменных, на которых функция принимает нулевые значения, записать дизъюнкции, инвертируя те переменные, которым соответствуют единичные значения. Затем дизъюнкции соединить знаками конъюнкции.
Например, пусть логическая функция задана прежней таблицей истинности, представленной на рис. 9а. Для наборов 0, 1, 2, 4 записываем элементарные дизъюнкции:
(
+
+
)
(
+
+
)
(
+
+
)
(
+
+
).
Дизъюнкции соединяем знаками конъюнкции и получаем функцию в СКНФ:
F(
,
,
)=(
+
+
)(
+
+
)(
+
+
)(
+
+
).
При построении ЭВМ широко используются компоненты, работа которых описывается функциями, представленными в дизъюнктивных формах. Поэтому целесообразно в дальнейшем рассматривать эти формы логических функций.
Законы и формулы алгебры логики
Закон двойного отрицания:
.Первый закон де Моргана:
.Второй закон де Моргана:
.Выражение коимликации через конъюнкцию:
.Выражение импликации через дизъюнкцию:
.Выражение эквивалентности через дизъюнкцию и конъюнкцию:
.Первый закон поглощения:
.Второй закон поглощения:
.
.
.Законы коммутативности:
Законы ассоциативности:
.
.
Законы идемпотентности:
.
.
Законы дистрибутивности:
.
.
,
,
.
,
.
Способы решения логических задач
Решение логических задач с помощью составления логических выражений
Логические задачи обычно формулируются на естественном языке. В первую очередь их необходимо формализовать, т.е. записать на языке алгебры высказываний. Полученные логические выражения необходимо упростить и проанализировать. Для этого иногда бывает необходимо построить таблицу истинности полученного логического выражения.
При формализации необходимо учитывать следующее соответствие между логическими операциями и правилами русского языка:
• Отрицание – частица «не»;
• Дизъюнкция – союз «или»;
• Конъюнкция – союзы «и», «а», «но», «хотя», «однако»;
• Эквиваленция – слова «в том и только в том случае», «тогда и только тогда» и другие;
• Импликация – слова «если, то».
Рассмотрим пример. В школе-новостройке в каждой из двух аудиторий может находиться либо кабинет информатики, либо кабинет физики. На аудиториях повесили шутливые таблички. На первой аудитории повесили табличку «По крайней мере, в одной из этих аудиторий размещается кабинет информатики», а на второй аудитории – табличку с надписью «Кабинет физики находится в другой аудитории». Проверяющему, который пришел в школу, известно только, что надписи на табличках или обе истинны, либо обе ложны. Помогите проверяющему найти кабинет информатики.
Решение.
Переведем условие на язык логики высказываний. Так как в каждой из аудиторий может находиться кабинет информатики, то пусть:
A – «В первой аудитории находится кабинет информатики»;
B – «Во второй аудитории находится кабинет информатики».
Тогда отрицаниям этих высказываний будут соответствовать:
- Высказывание, содержащееся на табличке
первой аудитории, соответствует
логическому выражению: X=A
B.
- «В первой аудитории находится кабинет
физики»,
- «Во второй аудитории находится кабинет
физики»,
- Высказывание, содержащееся на табличке
второй аудитории, соответствует
логическому выражению: Y=
.
Содержащееся в условии задачи утверждение
о том, что надписи на табличках либо
одновременно истинные, либо одновременно
ложные, в соответствии с законом
исключенного третьего записываются
следующим образом:
= 1.
Подставим вместо X и Y соответствующие формулы:
=
Упростим сначала первое слагаемое. В
соответствии с законом дистрибутивности
умножения относительно сложения:
=
.
В соответствии с законом непротиворечия:
=
.
Упростим теперь второе слагаемое. В
соответствии с законом де Моргана и
законом двойного отрицания:
=
.
В соответствии с законом непротиворечия:
.
В результате получаем:
.
Полученное логическое выражение
оказалось простым и поэтому его можно
проанализировать без построения таблицы
истинности. Для того чтобы выполнялось
равенство
,
обе логические переменные должны быть
равны 1, а соответствующие им высказывания
истинны.
Ответ:В первой аудитории находится кабинет физики, а во второй – кабинет информатики.
Табличный способ решения логических задач
Задача «Летние каникулы».Четверо друзей — Алик, Володя, Миша и Юра — собрались в доме у Миши. Мальчики оживленно беседовали о том, как они провели лето.
— Ну, Балашов, ты, наконец, научился плавать? — спросил Володя.
— О, еще как, — ответил Балашов, — могу теперь потягаться в плавании с тобой и Аликом.
— Посмотрите, какой я гербарий собрал, — сказал Петров, прерывая разговор друзей, и достал из шкафа большую папку.
Всем, особенно Лунину и Алику, гербарий очень понравился. А Симонов обещал показать товарищам собранную им коллекцию минералов.
Назовите имя и фамилию каждого мальчика.
Решение:Составим таблицу, где заголовки строк – это фамилии друзей, а заголовки граф – их имена.
|
|
Балашов |
Петров |
Лунин |
Симонов |
|
Алик |
- |
- |
- |
+ |
|
Володя |
- |
- |
+ |
- |
|
Миша |
- |
+ |
- |
- |
|
Юра |
+ |
- |
- |
- |
То, что Балашов разговаривает с Володей, позволяет поставить минус в ячейке, расположенной на пересечении строки «Балашов» и графы «Алик». Из того, что ребята собрались в доме у Миши, а Петров стал им демонстрировать свой гербарий, находящийся в шкафу, следует, что Миша и есть Петров. Это позволяет поставить плюс в ячейке, расположенной на пересечении строки «Петров» и графы «Миша», а также заполнить минусами все пустые клетки в строке «Петров» и графе «Миша». Гербарий понравился Лунину и Алику, значит, это два разных человека, следовательно, можно поставить минус в ячейке, расположенной на пересечении строки «Лунин» и графы «Алик». Из первой строки таблицы следует, что фамилия Юры – Балашов. Из первой графы таблицы следует, что фамилия Алика – Симонов. Единственная пустая ячейка на пересечении строки «Лунин» и графы «Володя» говорит о том, что фамилия Володи – Лунин. Таким образом, фамилия Алика – Симонов, Володи – Лунин, Миши – Петров и Юры – Балашов.