Алексей борис и михаил нашли в земле старинный сосуд решение

(логическое  умножение)

F =
А
Λ
B

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

Например, рассмотрим составное
высказывание “2*2=4 и 3*3=10”. Первое
простое высказывание (2*2=4) истинно (А=1),
а второе высказывание (3*3=10) ложно (В=0),
по таблице определяем, что логическая функция принимает значение 
ложь (F=0), т.е.
данное составное высказывание ложно.

(логическое  сложение)

F =
А
V
B

Например, рассмотрим составное высказывание
“2*2=4 или 3*3=10”. Первое простое
высказывание (2*2=4) истинно (А=1), а
второе высказывание (3*3=10) ложно (В=0),
по таблице определяем, что логическая функция принимает значение 
истина (F=1),
т.е. данное составное высказывание истинно.

(логическое отрицание)

F =
¬А

Например,

А=(2*2=4)=1(ИСТИНА)     
¬А
= 0

В=(3*3=10)=0(ЛОЖЬ)          

¬В = 1

(логическое следование)

F =
А
=>
B

Логическое следование(импликация) образуется соединением
двух высказываний в одно  с помощью оборота речи “если…,
то …”

(логическое равенство)

F =
А
 <=>
B

Логическое равенство(эквивалентность) образуется
соединением двух высказываний в одно  с помощью оборота речи

“…тогда и только тогда, когда
…”

преобразования логических выражений

1. ¬¬А
   = А (закон двойного отрицание)
2. ¬(А
   Λ В)
   = ¬А
   V ¬B   
   ( законы
3. ¬(А
   V В)
   = ¬А
   Λ ¬B           
   Моргана)
4. А =>
   В = ¬А
   V
   B
5. ¬(А =>
   В) = А
   Λ ¬B
6. А <=>
   В =(А
   Λ
   B) V (¬А
   Λ ¬B)
7. А
   Λ ¬А
   = 0 (закон непротиворечия)
8. А
   V
   ¬А
   = 1 (закон
   исключенного третьего)

(А
Λ В)
≡ (В
Λ
А) ;

(А

V
В) ≡ (В
V
А) ;

Законы ассоциативности:

(А V
В) V С ≡
А V (В V
С);

(А Λ
В) Λ С ≡
А Λ (В Λ
С);

Законы дистрибутивности:

А Λ (В
V С) ≡ (А Λ
В) V (А Λ
С)

А V (В
Λ С) ≡ (А V
В) Λ (А V
С)

Задача №43 стр. 59 :

Алеша, Боря и Гриша нашли в земле старинный сосуд. Рассматривая
удивительную находку, каждый высказал по два предложения:

Алеша: “Это сосуд греческий и изготовлен в V
веке”.     Боря: “Это сосуд финикийский и изготовлен
в  III веке”. Гриша: “Это сосуд не
греческий и изготовлен в IV веке”. Учитель
истории сказал ребятам, что каждый из них прав только в одном из двух
предложений. Где и в каком веке изготовлен сосуд?

Решение:

А  = “Это
сосуд греческий”;  

B
= ” Изготовлен в V
веке”;

C
= ” Изготовлен в IV веке
“;  

D
= “Изготовлен в  III
веке”;

E
= “Это сосуд финикийский “.                   

1. Если А =1(истина) , то В=0;     А=1,то Е=0,
тогда D=1;    
¬А=0, С=0, а это не
может быть, по условию ¬А или С истина.

2. Пусть А=0 и В=1;   Тогда
Е=1 а D=0;   и 
¬А=1, то С=0; 
в итоге получим  В=1 и Е=1, т. е. сосуд
финикийский и изготовлен в
V веке.

В нарушении правил обмена валюты
подозреваются четыре работника банка – А, В, С и D.
Известно, что:

1. Если А нарушил, то и В нарушил правила обмена валюты.
2. Если В нарушил, то и С нарушил или А не нарушил.
3. Если D не нарушил, то А нарушил, а С
   не нарушил.
4. Если D нарушил, то и А нарушил.

Кто из подозреваемых нарушил правила обмена валюты?  Решите
задачу с помощью логических операций.

Решение:

1. А => B;
2. B => C V
   ¬А;
3. ¬D => A Λ
   ¬C;
4. D => A

Произведение всех высказываний  =1.

( А
=> B)Λ(B
=> C V
¬А)Λ(¬D
=> A Λ ¬C)Λ (D
=> A) = 1

а
выражение справедлива тогда и только тогда, когда

А => B = 1;   
B => C V
¬А)
= 1;   ¬D => A Λ ¬C = 1;   
D => A = 1;

Составим таблицу истинности
для этого выражения:

Ответ:   А=1,B=1,C=1,D=1, 
т.е. все подозреваемые нарушили правила обмена валюты.

Графический подход.

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

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

Карта Карно функции трех переменных :

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

Пример 13.

Минимизировать , заданную ее СДНФ (пример 7) с помощью карты Карно.

Решение.

Карта Карно функции:

Итак:

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

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

Пример 14.

Упростить логическую функцию .

Решение.

Перечислим конституенты1 данной функции:

Составим карту Карно для этой функции:

Окончательно:

.

Алгоритмы решения логических задач

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

Последовательность решения логической задачи:

а) обозначение символами исходных и разыскиваемых высказываний;

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

в) вычисление значений полученного выражения при всех возможных комбинациях истинности и ложности исходных высказываний или преобразование сложного выражения к виду, который однозначно дает ответ;

г) проверка полученного решения по условию задачи.

Пример 15.

Дана логическая задача. Алексей, Борис и Валерий нашли в земле сосуд. Рассматривая удивительную находку, они выразили предположения:

Алексей: «Это греческий сосуд и изготовлен в V веке»;

Борис: «Это финикийский сосуд и изготовлен в III веке»;

Валерий: «Это сосуд не греческий и изготовлен в IV веке».

Впоследствии оказалось, что каждый из них прав только в одном из двух предположений. Где и в каком веке изготовлен сосуд?

Решение.

Обозначим символами высказывания:

х1 – «Найденный сосуд греческий»,

х2 – «Найденный сосуд финикийский»,

х3 – «Сосуд изготовлен в V веке»,

х4 – «Сосуд изготовлен в III веке»,

х5 – «Сосуд изготовлен в IV веке».

Запишем сложные высказывания – предположения школьников:

х1х3 – «Сосуд греческий и изготовлен в V веке» (Алексей).

По условию задачи известно, что это высказывание ложно: Алексей прав только в чем-то одном, т.е. х1=1, х3=0 или х1=0, х3=1. Истинным же будет высказывание:

.

х2х4 – «Сосуд финикийский и изготовлен в III веке» (Борис).

Рассуждая аналогично, получим:

.

Высказывание Валерия определяет логическое равенство:

.

Итак, имеем систему уравнений:

,

,

.

Порассуждаем логически. Сосуд может быть изготовлен только в одной стране, то есть .

Сосуд может быть изготовлен только в одном веке:

, , .

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

Х = ()()().

Таким образом, решить задачу – значит указать, при каких значениях х1,х2, х3, х4, х5 сложное высказывание Х истинно.

Найти набор, при котором Х = 1 можно, вычисляя значения Х на всех возможных наборах, заполняя таблицу истинности.

Видно, что набор N=12 единственный, при котором Х=1. Комбинация истинных высказываний: сосуд финикийский (х2=1) и изготовлен в V веке (х3=1).

Другой способ решения этой задачи заключается в упрощении функции Х(х1, х2, х3, х4, х5) с использованием основных тождеств, правил и законов алгебры логики.

Произведем преобразования:

Х = () ()() =

= .

Учитывая, что х1х2= 0 и х3х4= 0 :

Х = =

=.

Учитывая, что и , окончательно получим:

Х = .

Это означает, что Х = 1 только при совпадении: х1 = 0, х2 = 1, х3 = 1, х4 = 0, х5 = 0, т.е. сосуд – финикийский, изготовлен в V веке.

Пример 16.

Вернувшись домой, Мегрэ позвонил на набережную Орфевр.

• Говорит Мегрэ. Есть новости?

• Да, шеф. Поступили сообщения от инспекторов. Торранс установил, что если Франсуа был пьян, то либо Этьен убийца, либо Франсуа лжет. Жуссье считает, что Этьен – убийца, или Франсуа не был пьян, и убийство произошло после полуночи. Инспектор Люка просил передать, что если убийство было совершено после полуночи, то либо Этьен убийца, либо Франсуа лжет. Затем звонила … .

• Все. Спасибо. Этого достаточно. – Комиссар положил трубку. Он знал, что трезвый Франсуа никогда не лжет. Теперь он знал все.

Какой вывод сделал Мегрэ?

Решение.

Рассмотрим высказывания:

х1 – «Франсуа был пьян»,

х2 – «Этьен – убийца»,

х3 – «Франсуа лжет»,

х4 – «Убийство произошло после полуночи».

Выразим высказывания инспекторов формулами (составные высказывания).

Торранс: (Импликация – «если … то»).

Жуссье: .

Люка: .

Так как эти высказывания предполагаются истинными, то истинной будет и их конъюнкция F:

.

Освободимся от импликации с помощью формулы :

.

Раскрыв скобки и выполнив несложные преобразования, получим:

.

Таким образом, из показаний инспекторов следует, что или Этьен убийца, или одновременно имели место три обстоятельства: Франсуа солгал (х3), Франсуа не был пьян (), убийство произошло после полуночи (х4).

Так как («Трезвый Франсуа не лжет»), то .

Следовательно, истинно х2, то есть убийца – Этьен.