Где и в каком веке изготовлен сосуд?

С помощью Булевой переменной введем обозначения:

- Это сосуд греческий – ;

- Изготовлен в 5 веке – ;

- Это сосуд финикийский – ;

- Изготовлен в 3 веке – ;

- Это сосуд не греческий – ;

- Изготовлен в 4 веке – .

В этих обозначениях высказывания ребят кодируются логическими функциями следующим образом:

Алеша:

Боря:

Гриша:

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

,

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

Будем считать все =1, тогда получим следующую систему уравнений Булевой алгебры:

(1)

Система (1) представляет математическую модель искомой задачи. Один из способов решения (1) состоит в подборе тех единичных термов логических функций , наборы переменных которых удовлетворяют системе (1), а значения переменных из этих наборов не противоречат друг другу.

Для нахождения всех единичных термов системы (1) необходимо произвести вычисление таблиц функций f ₁, f ₂, f ₃, f ₄, f ₅. Это можно сделать с помощью программы Microsoft Excel. Для этого напишем программу на языке макрокоманд. Так как любая программа требует отладки, будем проводить её посредствам сравнения получающихся в процессе написания программы результатов с образцами, представленными в виде рисунков.

1. Включение компьютера и вход в систему. Результат выполнения представлен на рисунке 1.

Рис. 1.

2. Запуск программы Microsoft Excel.

Параметры: - рабочий стол. Результат выполнения представлен на рисунке 2.

Рис. 2.

3. Выбор активного листа.

Параметры: - лист: «Лист1». Результат выполнения представлен на рисунке 3.

Рис. 3.

4. Занесение заголовка в ячейку.

Параметры: - ячейка: A1, B1; - данные: «X₁», «X₅». Результат выполнения частично представлен на рисунке 4. Рис. 4.

5. Занесение целых чисел в ячейку.

Параметры: - ячейка: A2÷A5; - данные: «1», «1», «0», «0». Результат выполнения частично представлен на рисунке 5. Рис. 5.

6. Занесение целых чисел в ячейку.

Параметры: - ячейка: A2÷A5; - данные: «1», «0», «1», «0». Результат выполнения частично представлен на рисунке 6. Рис. 6.

7. Занесение заголовка в ячейку.

Параметры: - ячейка: C1, D1, E1, F1, G1; - данные: «не X₁», «не X₅», «X₁ и не X₅», «не X₁ и X₅», «E1 или F1». Результат выполнения частично представлен на рисунке 7.

Рис. 7.

8. Автозаполнение - формула.

Параметры: - ячейка: C2; - данные: «=НЕ(A2)» - конечная ячейка: C5. Результат выполнения представлен на рисунке 8. Рис. 8.

Аналогичным способом достроим таблицу истинности для функции f ₁, используя функции И, ИЛИ. В результате получим значения для х₁ и х₅, представленные на рис. 9.

Рис. 9.

Построим таблицы истинности для функций f ₂ – f ₅, проводя аналогичные действия с переменными (Рис. 10):

Рис. 10.

Таблица 1. Таблица 2. Таблица 3.

x1	x5	f 1		x2	x3	f 2		x1	x4	f 3

Таблица 4. Таблица 5.

x3	x4	x5	f 4		X1	x2	f 5

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

В качестве таковых наборов переменных возьмём следующие:

Из этих наборов переменных следует, что решение имеет вид:

(2)

Непротиворечивость решения (2) надо понимать так: значение х₁=0 имеет место в наборах переменных для функций f ₅, f ₁, f ₃ аналогично х₅=1 имеет место для f ₁, f ₄ и т.д.

Для проверки решения (2) подставим его в систему (1) и убедимся в том, что после этого уравнения системы (1) превращаются в тождества.

Для воспроизведения решения (2) в словесной форме необходимо вспомнить высказывания, которые кодировались символами х _i. Из принятой кодировки следует, что х₂=1 означает, что сосуд – финикийский, а х₅=1 – сосуд изготовлен в 5-ом веке.

Задача 2.

В школе произошло чрезвычайное происшествие: в классе кто-то из учеников разбил окно. Учителем были опрошены четыре ученика— Лёня, Дима, Толя и Миша. Каждый из учеников сделал по три заявления (см. таблицы 6 – 9). Учитель усомнился в одном из трёх заявлений каждого из опрошенных учеников. Последнее означает, что у каждого одно из трёх заявлений неверно. Из анализа всех заявлений необходимо узнать — кто разбил окно.

Таблица 6.

№	Показания Лёни	События	Вероятности	Переменные
	Я не виноват.
	Я не подходил к окну.
	Миша знает, кто разбил окно.

Таблица 7.

№	Показания Димы	События	Вероятности	Переменные
	Стекло разбил не я.
	С Мишей я не был знаком до поступления в школу.
	Это сделал Толя.

Таблица 8.

№	Показания Толи	События	Вероятности	Переменные
	Я не виноват.
	Это сделал Миша.
	Дима говорит неправду, что я разбил окно.

Таблица 9.

№	Показания Миши	События	Вероятности	Переменные
	Я не виноват.
	Стекло разбил Лёня.
	Дима может поручиться за меня.

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

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

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

(3)

Здесь операция суммы событий заменена операцией дизъюнкции, а операция произведения— конъюнкцией. Такие законы обоснованы выше. Вероятность сложного события обозначим через . В теории вероятностей значения вероятности могут принимать весь спектр числовых значений от нуля до единицы. Применительно к данной задаче будем считать, что вероятности Р принимают только предельные значения: нуль или единица. Это позволяет отождествлять вероятность с Булевой переменной , т.е. ввести обозначения:

В этом случае означает истинность данного события, а — ложность. Аналогично говорит об истинности сложного события , а — об его ложности.

Теперь, согласно теоремам о вероятности суммы и произведения нескольких событий, вероятность сложного события определяется следующим образом:

(4)

Проводя аналогичные рассуждения для показаний остальных учеников, и используя обозначения таблиц 2 – 4, заявления Димы, Толи и Миши представим в форме следующих математических соотношений:

(5)

(6)

(7)

Все эти логические формулы однотипны и представляют совершенную дизъюнктивную нормальную форму (СДНФ) одной и той же логической функции .

(8)

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

Таблица 10.

	0 0 0 0 0 1 0 1 0 0 1 1
	1 0 0 1 0 1 1 1 0 1 1 1

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

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

Единичные термы можно вычислять с помощью операций конъюнкции и отрицания по следующим формулам:

(9)

Поскольку в формулах (9) главной операцией считается операция конъюнкции, то единичные термы называют конъюнктивными термами. Если три конъюнктивных терма объединить знаком дизъюнкции, то согласно теории логических функций, получим аналитическое представление функции в форме СДНФ (8).

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

9. Выбор активного листа.

Параметры: - лист: «Лист2». Результат выполнения представлен на рисунке 10.

Рис. 10.

Все вычисления производятся по технологии, аналогичной той, которая была описана ранее, в пунктах 4 – 8. В результате вычислений получим таблицу, представленную на рис. 11.

Рис. 11.

Из таблицы, представленной на рис. 11, формируем таблицу 11, состоящую из конъюнктивных термов функций и соответствующих им наборов переменных.

Таблица 11.

f1

f2

f3

f4

x1

x2

x3

F^1J

y1

y2

y3

F^2J

z1

z2

z3

F^3J

s1

s2

s3

F^4J

F^13

F^23

F^33

F^43

F^15

F^25

F^35

F^45

F^16

F^26

F^36

F^46

Здесь применительно к функции f_i конъюнктивный терм обозначен через Fⁱ_J так, что верхний индекс i соответствует номеру логической функции.

Если никто из учеников не отказался от своих высказываний, то значение всех логических функций надо положить равными единице, после чего соотношения (4) – (7) примут вид следующей системы алгебраических уравнений для определения двенадцати неизвестных, которые представляются показаниями учеников в обозначениях таблиц 6 – 9:

(10)

Здесь для обозначения конъюнктивных термов, входящих в использован символ . Соотношения (10) представляют математическую модель показаний учеников и их следует называть системой уравнений Булевой алгебры, так как они определены на множестве М = {0;1} с использованием трёх логических операций – дизъюнкции, конъюнкции и отрицания.

В этой системе число неизвестных превышает число уравнений. Однако, так как 1Ú0=1, то решение системы (10) будет определяться такими четырьмя термами: F¹ _j, F² _j, F³ _j, F⁴ _j, (j=3, 5, 6), наборы переменных, которых после подстановки в (10) и проведения логических вычислений превратят уравнение (10) в тождества. При этом термы Fⁱ_J вычисляются по формуле (9) с учётом обозначения переменных согласно таблице 11.

Среди комбинаций из указанных четырёх термов могут оказаться такие, значения наборов переменных которых могут привести к противоречивым показаниям учеников. Например, рассмотрим термы F¹₃, F²₃, F³₃, F⁴₃.

Наборы переменных, соответствующие указанным термам, определяются по таблице 11. В таблице 12 приведены значения переменных, найденные из полученных наборов переменных, а также показания учеников, соответствующие данным значениям переменных.

Чтобы показать, что значения переменных из таблицы 12 суть решение системы (10) необходимо для этих значений вычислить по (9) строки и подставить их в тождества.

Здесь же в таблице 12 даются высказывания мальчиков, соответствующие рассмотренному решению. Из них следует, что все ученики виноваты. Последнее противоречит условию задачи.

Такое решение задачи в дальнейшем будем называть противоречивым

Таблица 12.

F^13=1	Показания Лёни.
x1=0 x2=1 x3=1	Я виноват. Я не подходил к окну. Миша знает, кто разбил окно.
F^23=1	Показания Димы.
y1=0 y2=1 y3=1	Стекло разбил я. С Мишей я не был знаком до поступления в школу. Это сделал Толя.
F^33=1	Показания Толи.
z1=0 z2=1 z3=1	Я виноват. Это сделал Миша. Дима говорит неправду, что я разбил окно.
F^43=1	Показания Миши.
s1=0 s2=1 s3=1	Я виноват. Стекло разбил Лёня. Дима может поручиться за меня.

Рассмотрим другое решение: F¹₃=1, F²₆=1, F³₅=1, F⁴₆=1. Значения переменных и показания учеников, соответствующие этому решению, приведены в таблице 13.

Таблица 13.

F^13=1	Показания Лёни.
x1=0 x2=1 x3=1	Я виноват. Я не подходил к окну. Миша знает, кто разбил окно.
F^26=1	Показания Димы.
y1=1 y2=1 y3=0	Стекло разбил я. С Мишей я не был знаком до поступления в школу. Это не сделал Толя.
F^35=1	Показания Толи.
z1=1 z2=0 z3=1	Я не виноват. Это не сделал Миша. Дима говорит неправду, что я разбил окно.
F^46=1	Показания Миши.
s1=1 s2=1 s3=0	Я не виноват. Стекло разбил Лёня. Дима не может поручиться за меня.

Непротиворечивые показания этой таблицы говорят о том, что Лёня виноват и он разбил окно.

Решение, приводящее к логически непротиворечивому результату, назовём непротиворечивым.

Возникает вопрос: Как из множества решений выбрать одно – непротиворечивое?

Вернёмся к первоначальным заявлениям учеников (таблицы 6 – 9) и обратим внимание на то, что из четырёх заявлений – x₁, y₁, z₁, s₁ одно не верно.

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

(11)

Теперь значения переменных из таблицы 13 подставим в правую часть формулы (11) и произведём вычисление f с помощью программы Microsoft Excel. Для этого продолжим написание программы на языке макрокоманд.

10. Выбор активного листа.

Параметры: - лист: «Лист2». Результат выполнения представлен на рисунке 11. Рис. 11.

11. Занесение заголовка в ячейку.

Параметры: - ячейка: A1, B1, C1, D1; - данные: «X₁», «Y₁», «Z₁», «S₁». Результат выполнения частично представлен на рисунке 12. Рис. 12.

12. Занесение целых чисел в ячейку.

Параметры: - ячейка: A2÷D2; - данные: «0», «1», «1», «1». Результат выполнения частично представлен на рисунке 13. Рис. 13.

13. Занесение заголовка в ячейку.

Параметры: - ячейка: E1, F1, G1, H1, I1, J1, K1, L1, M1; - данные: «не X₁», «не Y₁», «не Z₁», «не S₁», «E1 и B1 и C1 и D1», «A1 и F1 и C1 и D1», «A1 и B1 и G1 и D1», «A1 и B1 и C1 и H1», «I1 или J1 или K1 или L1». Результат выполнения частично представлен на рисунке 14.

Рис. 14.

14. Автозаполнение - формула.

Параметры: - ячейка: E2; - данные: «=НЕ(A2)» - конечная ячейка: H2. Результат выполнения представлен на рисунке 15.

Рис. 15.

15. Занесение формул в ячейку.

Параметры: - ячейка: I2; - данные: «=И(E2;B2;C2;D2)». Результат выполнения частично представлен на рисунке 16. Рис. 16.

Аналогичным образом рассчитаем значения, расположенные в ячейках J2, K2, L2 и M2. В данном случае получим: f = f _max=1. Результат выполнения частично представлен на рисунке 17.

Рис. 17.

Проведём расчёт с целью вычисления f по (11) с использованием значений переменных из таблицы 12; тогда будем иметь: f = f _min=0 (Рис. 18).

Рис. 18.

Таким образом, непротиворечивое решение приводит к максимальным значениям логической функции (11). Последнее может означать, что логическая функция (11) представляется критерием отбора непротиворечивого решения системы (10) из множества решений. По аналогии с экономическими задачами линейного и нелинейного программирования, логическую функцию (11) следует назвать целевой функцией.

Теперь алгоритм решения данной задачи (10) – (11) сводится к следующему: перебираем всевозможные комбинации из четырёх термов F¹ _j, F² _j, F³ _j, F⁴ _j, затем применительно к каждой выбранной комбинации по таблице 11 определяем значения переменных, по которым вычисляем целевую функцию (11).

Тот вариант из четырёх единичных термов, который определит максимальное значение целевой функции (11), следует признать в качестве непротиворечивого решения.

Очевидно, что такой алгоритм требует большого объёма логических вычислений. Так, например, в рассматриваемой задаче, число комбинаций из четырех термов будет определяться числом сочетаний из двенадцати термов по четыре, т.е. =495

Задания для самостоятельной работы.

Задача 1. На заводе работали три друга: слесарь (с), токарь (т), шлифовщик (ш). Их фамилии: Борисов (Б), Иванов (В), Семенов (С).

Дополнительные сведения об указанных лицах таковы:

1 – у слесаря нет ни братьев, ни сестер;

2 – слесарь самый младший из друзей;

3 – Семенов женат на сестре Борисова;

4 – Семенов старше токаря.

Необходимо узнать: у кого какая специальность?

Ответ: Семенов – шлифовщик; Иванов – слесарь; Борисов – токарь.

Задача 2. В одном королевстве были незамужние принцессы, голодные тигры и приговоренный к казни узник. Но всякому узнику, осужденному на смерть полагалось угадать, в какой из двух комнат находиться тигр, а в какой принцесса. Хотя вполне могло быть, что король в обеих комнатах разместил принцесс, или что хуже, в обеих – тигров. Выбор надо было сделать на основании табличек на дверях комнат. Причём узнику было известно, что утверждения на табличках либо оба истинны, либо оба ложны. Надписи гласили:

Какую дверь должен выбрать узник?

Ответ: в первой комнате – тигр, во второй – принцесса.

Задача 3. На соревнованиях по лёгкой атлетике Андрей, Боря, Серёжа и Володя заняли первые четыре места. Но когда девочки стали вспоминать, как эти места распределились между победителями, то мнения разошлись:

Даша: Андрей был первым, а Володя – вторым.

Галя: Андрей был вторым, а Борис – третьим.

Лена: Боря был четвёртым, а Серёжа – вторым.

Ася, которая была судьёй на этих соревнованиях и хорошо помнила как распределились места сказала, что каждая из девочек сделала одно правильное и одно неправильное заявление.

Кто из мальчиков и какое место занял?

Ответ: Андрей занял первое место, Серёжа – второе, Боря – третье, Володя – четвёртое.

Дата добавления: 2015-06-26