2020-05-21
142
| x1 | x5 | f 1 | x2 | x3 | f 2 | x1 | x4 | f 3 | |||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | |||
| 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | |||
| 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | |||
| 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
Таблица 4. Таблица 5.
| x3 | x4 | x5 | f 4 | x1 | x2 | f 5 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 1 | 0 | 1 | 1 | |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 | |
| 1 | 0 | 0 | 1 | ||||
| 1 | 0 | 1 | 0 | ||||
| 1 | 1 | 0 | 0 | ||||
| 1 | 1 | 1 | 0 |
В таблицах 1 – 5 единичные наборы определяются теми наборами переменных, при которых логические функции имеют единичные значения. Для решения поставленной задачи необходимо выбрать пять единичных термов, значения переменных в которых не противоречивы.
В качестве таковых наборов переменных возьмём следующие:
Из этих наборов переменных следует, что решение имеет вид:
(2)
Непротиворечивость решения (2) надо понимать так: значение х1=0 имеет место в наборах переменных для функций f5, f1, f3 аналогично х5=1 имеет место для f1, f4 и т.д.
|
|
|
Для проверки решения (2) подставим его в систему (1) и убедимся в том, что после этого уравнения системы (1) превращаются в тождества.
Рис. 4
Для воспроизведения решения (2) в словесной форме необходимо вспомнить высказывания, которые кодировались символами хi. Из принятой кодировки следует, что 
означает, что граната – оборонительная, а 
– радиус разлета осколков равен 150 м.
Задача 2. В школе произошло чрезвычайное происшествие: в классе кто-то из учеников разбил окно. Учителем были опрошены четыре ученика – Лёня, Дима, Толя и Миша. Каждый из учеников сделал по три заявления (см. таблицы 1–4). Учитель усомнился в одном из трёх заявлений каждого из опрошенных учеников. Последнее означает, что у каждого одно из трёх заявлений неверно. Из анализа всех заявлений необходимо узнать – кто разбил окно. Таблица 6.
| № | Показания Лёни | События | Вероятности | Переменные |
| 1 | Я не виноват. | 
| 
| 
|
| 2 | Я не подходил к окну. | 
| 
| 
|
| 3 | Миша знает, кто разбил окно. | 
| 
| 
|
Таблица 7.
| № | Показания Димы | События | Вероятности | Переменные |
| 1 | Стекло разбил не я. | 
| 
| 
|
| 2 | С Мишей я не был знаком до поступления в школу. | 
| 
| 
|
| 3 | Это сделал Толя. | 
|
| 
|
Таблица 8.
| № | Показания Толи | События | Вероятности | Переменные |
| 1 | Я не виноват. | 
| 
| 
|
| 2 | Это сделал Миша. | 
| 
| 
|
| 3 | Дима говорит неправду, что я разбил окно. | 
|
| 
|
Таблица 9.
|
|
|
| № | Показания Миши | События | Вероятности | Переменные |
| 1 | Я не виноват. | 
| 
| 
|
| 2 | Стекло разбил Лёня. | 
| 
| 
|
| 3 | Дима может поручиться за меня. | 
| 
| 
|
Для получения вычислимого логического алгоритма решения данной задачи необходимо формализовать её условие, т.е. показаниям всех учеников придать форму математических соотношений, состоящих из символов, обозначающих понятия, и знаков логических операций, выполняемых над указанными символами.
С этой целью предположим, что каждое из показаний Лёни есть события , , 
, которые могут произойти или не произойти. Вероятности того, что каждое из названных событий имело место, обозначим соответственно 
, , 
. Вероятности же того, что события не имели место, обозначим через 
, 
, 
. При этом предполагается, что событие 
противоположно событию и т.д. применительно к оставшимся событиям.
Событие 
, состоящее в том, что из трёх показаний Лёни одно не верно, называется сложным событием. Оно составляется как комбинация простых событий следующим образом:
(3)
Здесь операция суммы событий заменена операцией дизъюнкции, а операция произведения – конъюнкцией. Такие законы обоснованы выше. Вероятность сложного события 
обозначим через 
. В теории вероятностей значения вероятности могут принимать весь спектр числовых значений от нуля до единицы. Применительно к данной задаче будем считать, что вероятности 
принимают только предельные значения: нуль или единица. Это позволяет отождествлять вероятность с Булевой переменной 
, т.е. ввести обозначения: 
, 
, 
, 
, 
В этом случае 
означает истинность данного события, а 
– ложность. Аналогично 
говорит об истинности сложного события , а 
- об его ложности.
Теперь, согласно теоремам о вероятности суммы и произведения нескольких событий, вероятность 
сложного события определяется следующим образом: 
(4)
Проводя аналогичные рассуждения для показаний остальных учеников, и используя обозначения таблиц 2 – 4, заявления Димы, Толи и Миши представим в форме следующих математических соотношений:
(5)
(6)
(7)
Все эти логические формулы однотипны и представляют совершенную дизъюнктивную нормальную форму (СДНФ) одной и той же логической функции 
. 
(8)
Придавая набору, 
различные комбинации из нулей и единиц, подставляя их в (8) и производя вычисления с помощью таблиц операций конъюнкции и дизъюнкции, получаем таблицу 10 логической функции 
.
Таблица 10.
|   
|
|
| 0 1 2 3 | 0 0 0 0 0 1 0 1 0 0 1 1 | 0 0 0 1 |
| 4 5 6 7 | 1 0 0 1 0 1 1 1 0 1 1 1 | 0 1 1 0 |
В таблице 10 через обозначен десятичный код набора переменных, представляющего множество трёхразрядных двоичных чисел.
Единичные значения логической функции называются единичными термами. Для них введём новое обозначение 
.
Единичные термы можно вычислять с помощью операций конъюнкции и отрицания по следующим формулам: 
(9)
Поскольку в формулах (9) главной операцией считается операция конъюнкции, то единичные термы называют конъюнктивными термами. Если три конъюнктивных терма объединить знаком дизъюнкции, то согласно теории логических функций, получим аналитическое представление функции в форме СДНФ (8).
|
|
|
Для получения явного вида конъюнктивных термов логических функций 
необходимо вычислить таблицы этих функций с помощью программы Microsoft Excel. Для этого:
6. В окне Microsoft Excel заполните ячейки А12¸С49 таблицы, перебрав все варианты значений логических переменных хj, уj, zj и sj;
Постройте таблицу истинности для функций Fij, воспользовавшись функциями НЕ, И, ИЛИ, которые находятся в мастере функций ƒх в категории ЛОГИЧЕСКИЕ. См. пп. 4 – 5.
В конечном итоге получаем таблицу, показанную на рис. 5.
Из таблицы, изображённой на рис. 5, формируем таблицу 11, состоящую из конъюнктивных термов функций 
и соответствующих им наборов переменных.
Таблица 11.
| f1 | f2 | f3 | f4 | ||||||||||||
| x1 | x2 | x3 | F1J | y1 | y2 | y3 | F2J | z1 | z2 | z3 | F3J | s1 | s2 | s3 | F4J |
| 0 | 1 | 1 | F13 | 0 | 1 | 1 | F23 | 0 | 1 | 1 | F33 | 0 | 1 | 1 | F43 |
| 1 | 0 | 1 | F15 | 1 | 0 | 1 | F25 | 1 | 0 | 1 | F35 | 1 | 0 | 1 | F45 |
| 1 | 1 | 0 | F16 | 1 | 1 | 0 | F26 | 1 | 1 | 0 | F36 | 1 | 1 | 0 | F46 |
Рис. 5
Здесь применительно к функции fi конъюнктивный терм обозначен через Fij так, что индекс i соответствует номеру логической функции.
Если никто из учеников не отказался от своих высказываний, то значение всех логических функций 
надо положить равными единице, после чего соотношения (4) – (7) примут вид следующей системы алгебраических уравнений для определения двенадцати неизвестных, которые представляются показаниями учеников в обозначениях таблиц 6 – 9:
(10)
Здесь для обозначения конъюнктивных термов, входящих в 
использован символ 
. Соотношения (10) представляют математическую модель показаний учеников и их следует называть системой уравнений Булевой алгебры, так как они определены на множестве М={0;1} с использованием трёх логических операций – дизъюнкции, конъюнкции и отрицания. В этой системе число неизвестных превышает число уравнений. Однако, так как 1Ú0=1, то решение системы (10) будет определяться такими четырьмя термами: F1j, F2j, F3j, F4j, (j=3, 5, 6), наборы переменных,
которых после подстановки в (10) и проведения логических вычислений превратят уравнение (10) в тождества. При этом термы Fij вычисляются по формуле (9) с учётом обозначения переменных согласно таблице 11.
|
|
|
Среди комбинаций из указанных четырёх термов могут оказаться такие, значения наборов переменных которых могут привести к противоречивым показаниям учеников. Например, рассмотрим термы F13, F23, F33, F43.
Наборы переменных, соответствующие указанным термам, определяются по таблице 11. В таблице 12 приведены значения переменных, найденные из полученных наборов переменных, а также показания учеников, соответствующие данным значениям переменных.
Чтобы показать, что значения переменных из таблицы 12 суть решение системы (10) необходимо для этих значений вычислить по (9) строки и подставить их в тождества.
Здесь же в таблице 12 даются высказывания мальчиков, соответствующие рассмотренному решению. Из них следует, что все ученики виноваты. Последнее противоречит условию задачи.
Такое решение задачи в дальнейшем будем называть противоречивым
Таблица 12.
| F13=1 | Показания Лёни. |
| x1=0 x2=1 x3=1 | Я виноват. Я не подходил к окну. Миша знает, кто разбил окно. |
| F23=1 | Показания Димы. |
| y1=0 y2=1 y3=1 | Стекло разбил я. С Мишей я не был знаком до поступления в школу. Это сделал Толя. |
| F33=1 | Показания Толи. |
| z1=0 z2=1 z3=1 | Я виноват. Это сделал Миша. Дима говорит неправду, что я разбил окно. |
| F43=1 | Показания Миши. |
| s1=0 s2=1 s3=1 | Я виноват. Стекло разбил Лёня. Дима может поручиться за меня. |
Рассмотрим другое решение: F13=1, F26=1, F35=1, F46=1. Значения переменных и показания учеников, соответствующие этому решению, приведены в таблице 13.
Таблица 13.
| F13=1 | Показания Лёни. |
| x1=0 x2=1 x3=1 | Я виноват. Я не подходил к окну. Миша знает, кто разбил окно. |
| F26=1 | Показания Димы. |
| y1=1 y2=1 y3=0 | Стекло разбил я. С Мишей я не был знаком до поступления в школу. Это не сделал Толя. |
| F35=1 | Показания Толи. |
| z1=1 z2=0 z3=1 | Я не виноват. Это не сделал Миша. Дима говорит неправду, что я разбил окно. |
| F46=1 | Показания Миши. |
| s1=1 s2=1 s3=0 | Я не виноват. Стекло разбил Лёня. Дима не может поручиться за меня. |
Непротиворечивые показания этой таблицы говорят о том, что Лёня виноват и он разбил окно.
Решение, приводящее к логически непротиворечивому результату, назовём непротиворечивым.
Возникает вопрос: Как из множества решений выбрать одно – непротиворечивое?
Вернёмся к первоначальным заявлениям учеников (таблицы 6–9) и обратим внимание на то, что из четырёх заявлений – x1, y1, z1, s1 одно не верно.
По аналогии с рассуждениями, приводящими к формулам (3) и (4), указанную особенность четырёх заявлений можно выразить так:
(11)
Теперь значения переменных из таблицы 13 подставим в правую часть формулы (11) и произведём вычисление f с помощью программы Microsoft Excel. Для этого:
1. В ячейках А52–D52 запишите значения переменных x1, y1, z1 и s1 из таблицы 13.
2. Далее, с помощью функций НЕ, И, ИЛИ найдём значение функции f.
В данном случае получим: f=fmax=1.
3. Аналогично вычислим f по (11) с использованием значений переменных из таблицы 12; тогда будем иметь: f = f min=0 (рис. 6).
Рис. 6
Таким образом, непротиворечивое решение приводит к максимальным значениям логической функции (11). Последнее может означать, что логическая функция (11) представляется критерием отбора непротиворечивого решения системы (10) из множества решений. По аналогии с экономическими задачами линейного и нелинейного программирования, логическую функцию (11) называют целевой функцией.
Теперь алгоритм решения данной задачи (10)–(11) сводится к следующему: перебираем всевозможные комбинации из четырёх термов F1j, F2j, F3j, F4j, затем применительно к каждой выбранной комбинации по таблице 11 определяем значения переменных, по которым вычисляем целевую функцию (11).
Тот вариант из четырёх единичных термов, который определит максимальное значение целевой функции (11), следует признать в качестве непротиворечивого решения.
Очевидно, что такой алгоритм требует большого объёма логических вычислений. Так, например, в рассматриваемой задаче, число комбинаций из четырех термов будет определяться числом сочетаний из двенадцати термов по четыре, т.е. 
=495
