ГЛАВА 1. ЛОГИКА И ЭЛЕМЕНТЫ СХЕМОТЕХНИКИ
 
 
 
   

АЛГЕБРА ЛОГИКИ

 
 
 
 
 1.
  
Логика - наука, изучающая методы доказательств и опровержений, то есть методы установления истинности или ложности одних высказываний (утверждений, суждений) на основе истинности или ложности других высказываний.  
  
 
 2.
  
Математическая логика - это современная форма логики, которая полностью опирается на формальные математические методы.
Частью математической логики является алгебра логики - раздел, изучающий строение сложных логических высказываний и способы установления их истинности с помощью алгебраических методов.  
  
 
 3.
  
Алгебру логики иногда называют алгеброй Буля, или булевой алгеброй, по имени ее создателя - Джоржа Буля - английского математика (кстати, отца Этель Л. Войнич, написавшей "Овод"). Основные результаты теории были сформулированы им в книге "Исследование законов мышления", изданной в 1854 году. Во введении Буль писал, что назначение трактата - исследовать основные законы тех операций ума, посредством которых производится рассуждение, выразить их на символическом языке некоторого исчисления и на этой основе установить науку логику и построить ее метод.
Глава содержит краткие сведения о логических переменных, основных операциях, построении и преобразовании логических функций.  
 
 
   

НАЧАЛЬНЫЕ СВЕДЕНИЯ

 
 
 
 
 4.
  
Основным объектом изучения математической логики являются элементарные высказывания.
Под термином "высказывание" мы будем понимать повествовательное предложение. При этом нас будет интересовать не построение: подлежащее - сказуемое - дополнение, а характерные свойства рассматриваемых образований: являются они истинными или ложными.  
Высказывания отличаются от других языковых образований тем, что мы можем присвоить им определенное значение истинности - "истина", если они истинны, значение "ложь", если они ложны. При этом мы исходим из "принципа исключенного третьего", или "третьего не дано", который состоит в том, что каждое высказывание или истинно, или ложно, и других возможностей нет. Ситуация, когда ни истинно, ни ложно, была бы и в обычном смысле неразрешимой. Этот принцип называют принципом двузначности.
Все научные знания (законы и явления физики, химии и биологии, математические теоремы и т.д.), события повседневной жизни, ситуации, возникающие в процессах управления, формулируются в виде высказываний.  
 
Примерами указанных высказываний являются:  
 
"35 делится на 7",  
"Москва - столица России".  
Все они имеют значение истинности "истина".  
Следующие высказывания имеют значение истинности "ложь":  
"Мышь больше слона",  
"Молодые лошади называются щенятами",  
"6 больше 8".  
Повелительные ("Войдите, пожалуйста!"), вопросительные ("Знаешь ли ты информатику?") и бессмысленные предложения не являются высказываниями.  
   
 
 5.
  
Если логика имеет дело со смыслом высказываний, то в алгебре логики работают с формулами. Любое элементарное высказывание обозначается малой буквой латинского алфавита (в нашем повествовании - х i ) , совершенно так же, как в элементарной алгебре обозначаются величины, когда мы абстрагируемся от того, какие именно предметы изучаются, нас интересует только их количество и соотношение между ними.  
Поскольку высказывание может принимать одно из двух значений, то говорят о "переменных высказываниях". Это означает, что рассматривается не только конкретно определенное высказывание хi , но также некоторая логическая переменная х i , которую можно использовать для обозначения произвольного высказывания. Замещение переменной конкретным высказыванием означает предоставления одного из значений "истина" или "ложь".  
  
 
 6.
  
Итак, в алгебре логики в каждом высказывании мы будем отвлекаться от всех особенностей высказывания, кроме одного - истинно оно или ложно. Истинное высказывание условно обозначается единицей (если x1 - высказывание " 35 делится на 7", то x1 = 1), а ложное - нулем (если x2 - высказывание "мышь больше слона", то x2 = 0).  
  
 
 7.
  
Таким образом, диапазон изменения переменного - xi в алгебре логики существенно меньше, чем изменение переменного в элементарной алгебре: оно принимает только одно из двух значений - или 1, или 0.  
  
 
 8.
  
Из элементарных высказываний с помощью логических связок " и", "или", "не", "если : то" и других (логических операций) строятся сложные высказывания - формулы (или функции ) алгебры логики.
  Способы построения новых высказываний из заданных с помощью логических связок, их преобразования и установления истинности изучаются в логике высказываний с помощью алгебраических методов.  
  
 
 9.
  
Сущность алгебраического подхода к логике поясним на примере элементарной алгебры - алгебры арифметики. Основные объекты алгебры арифметики - выражения (формулы), состоящие из букв, знаков операций и скобок. С формулами производят процедуры двух типов: вычисления и преобразования.  
 
Вычисления - вместо букв подставляют числа, знаки указывают действия, а скобки их порядок. Каждая формула задает функцию. Переменные - буквы формулы.  
 
Преобразование формулы происходит так: исходная формула или ее часть F1 заменяется другой, в результате получается новая формула F2, которая эквивалентна F1 (т.е. при любых значениях аргументов F1 и F2 дают один и тот же результат). Преобразование выражений производится на основе законов арифметики, а также полученных из них соотношений типа (a + b) 2 = a 2 + 2ab + b 2 и т.п.   
По аналогии строится алгебра логики. Она рассматривает логические выражения как алгебраические, которые можно преобразовать по определенным правилам. Разница заключается в том, что в выражениях алгебры логики переменные являются логическими (0 и 1). Знаки операций обозначают логические операции (логические связки).   
  
 
 10.
  
В логических задачах исходными данными являются суждения, подчас неожиданные и нередко весьма запутанные. Высказывания и связи между ними бывают иногда столь противоречивыми, что такие "твердые орешки" не под силу "раскусить" и вдумчивому математику.  
В данных случаях большую помощь может оказать ЭВМ как необходимый инструмент эффективного решения логических задач с многими переменными. В настоящее время нет ни одного языка программирования, который не включал бы логических операций.  
 
 
   

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ

 
 
 
 
 11.
  
В алгебре логики основными (элементарными) операциями являются отрицание, логическое сложение (дизъюнкция), логическое умножение (конъюнкция), импликация, эквивалентность.   
  
 
 12.
  
Отрицание. Операция отрицания соответствует в обычном языке частице не. Функция, получающаяся в результате применения операции отрицания к высказыванию x , обозначается так: . Читается " не икс". Заметим, что в математической логике до сих пор нет единых обозначений, поэтому вместо можно встретить и другие обозначения, смысл которых тот же самый, например, или .   
  
 
 13.
  
Новое сложное высказывание - ложно при условии, что высказывание x истинно и истинно при условии, что x - ложно. Запишем эти зависимости в виде таблицы истинности (формальное определение дадим позднее) для операции отрицания:   
  
 
 
  

x

1

0

0

1
 
   
 
 14.
  
Пример 1. Обозначим суждение (высказывание) "Я иду в кино " через x 1, а суждение "Я достаю билеты в театр " через x 2 . Тогда в сложном суждении " Если я завтра достаю билеты в театр, то не иду в кино ( x 2 = 1, x 1 = 0), а если я не достану билеты в театр, то пойду в кино ( x 2 = 0, x 1 = 1)" высказывания x 1 и x 2 связаны между собой операцией отрицания: x 1 = .   
  
 
 15.
  
Логическое умножение (будем называть как в математической логике - конъюнкцией). Обозначается x1 x 2 Другие обозначения: x 1  ·  x 2, x 1& x 2.Читается " икс один и икс два". Это сложное суждение, которое истинно только в том случае, когда и суждение x1, и суждение x 2 истинны. В остальных случаях сложное высказывание ложно. Таблица истинности для конъюнкции (логического умножения):   
  
 
 
  

x 1

x 2

x 1 x 2

0

0

0

0

1

0

1

0

0

1

1

1
 
   
 
 16.
  
Пример 2 . Рассмотрим условия, необходимые для получения человеком водительских прав. Суждение " Человек получает права водителя" обозначим через y.  
Для получения прав необходимо получить положительное заключение медицинской комиссии о состоянии здоровья. Сформулируем высказывание " Человек здоров" и обозначим его x1.  
Кроме здоровья, надо еще сдать два экзамена: по вождению и по правилам дорожного движения (ПДД).  
Высказывания: x 2 - " Экзамен по вождению сдан успешно";  
x 3 - " Экзамен по ПДД сдан успешно".  
В символической записи имеем:  
 
y = x 1 x 2 x 3(или y = x 1 x 2 x 3 ).
 
Суждение y будет истинным ( y = 1) только в том случае, если истинны все три суждения: x 1 = 1, x 2 = 1 и x 3 = 1. При всех других комбинациях y = 0, то есть высказывание y ложно: человек не получит прав водителя.  
   
 
 17.
  
Логическое сложение (дизъюнкция). Обозначается x 1   x 2 . Читается "икс один или икс два". Знак " " взят из латинского языка, в котором есть союз "Vel", означающий или то, или другое, или то и другое вместе. Vel более точно определяет суть логического сложения, чем русский союз или , так как последний, кроме значения или то, или другое, или то и другое вместе , имеет еще и другое значение - или только то, или только другое.  
Логическое сложение выражает суждение (сложное высказывание), которое истинно в том случае, если хотя бы одно из суждений истинно.  
   
 
 
  
Таблица истинности логического сложения:  
   
 
 
  

x 1

x 2

x 1   x 2

0

0

0

0

1

1

1

0

1

1

1

1
   
 
 18.
  
Пример 3. Боря давно хотел иметь книгу "Основы информатики и вычислительной техники", где рассматриваются вопросы алгебры логики. Он попросил своих товарищей Андрея и Валерия, чтобы они обязательно купили для него эту книгу, если она им попадется. У Бориса будет книга (суждение y ) при выполнении равенства: 		   
 
 
  
y = x 1   x 2,
   
 
 
  
где x 1 - высказывание "Андрей купил книгу", 		   
 
 
  
x 2 - высказывание "Валерий купил книгу". 		   
 
 
  
Высказывание y = x 1   x 2, не исключает случая, что книгу купят и Андрей, и Валерий.  
   
 
 19.
  
Импликация. Обозначается x 1   x 2 . Логически реализует связку естественной речи " если : то". Импликация определяется следующим образом:  
   
 
 
  

x 1

x 2

x 1   x 2

0

0

1

0

1

1

1

0

0

1

1

1
 
   
 
 20.
  
Например, в профессиональной речи следователь часто логически рассуждает примерно так: "Если кража произошла до полуночи, то наверняка это совершил Вольдемар". Нетрудно заметить, что два высказывания: x 1 - " Кража произошла до полуночи"и x 2 - " Вор - Вольдемар" связаны операцией импликации x 1   x 2 		   
 
 
  
Данное умозаключение будет истинным, если при истинном x 1 истинно x 2 . Логическое выражение будет ложным, если при истинном x 1 оказывается ложным x 2. 		   
 
 
  
Замечание. Если x 1  = 0 (высказывание - предположение ложно, или, говорят, ложная посылка), то x 2( следствие) может быть как истинным ("Вор - Вольдемар", x 2  =1), так и ложным ("Вор - не Вольдемар", x 2  = 0). Но логического смысла выражение не имеет.  
   
 
 21.
  
Данное положение вещей выражается с помощью поговорки " ex falso guod libet", или " из ложной посылки можно вывести всякое".  
   
 
 
  
В обычной речи такие высказывания не имеют значения, поскольку выражения типа " Если кто-то сумасшедший, то 5 меньше 2" рассматриваются как бессмысленные. Это связано с тем, что в обычной речи предусматривается содержательная связь, причинные отношения между посылкой (причиной) x 1 и заключением (следствием) x 2, которые здесь не заданы. Такая содержательная связь не может быть описана с помощью логики высказываний.  
   
 
 22.
  
Эквивалентность . Эквивалентностью (или эквиваленцией) двух высказываний x 1  и x 2  называется новое высказывание, которое считается истинным, когда оба высказывания x 1  и x 2  либо одновременно истинны, либо одновременно ложны, и ложным - во всех остальных случаях.  
   
 
 
  
Эквивалентность высказываний x 1  и x 2  обозначается символом x 1  x 2 (или x 1 =  x 2, или x 1  x 2), читается " для того, чтобы x 1, необходимо и достаточно, чтобы x 2" или " x 1 тогда и только тогда, когда x 2". Высказывания x 1 и x 2 называются членами эквивалентности.  
   
 
 23.
  
Логические значения операции эквивалентности описываются следующей таблицей истинности.  
   
 
 
  

x 1

x 2

x 1  x 2

0

0

1

0

1

0

1

0

0

1

1

1
 
   
 
 24.
  
Например, эквивалентность " Треугольник SPQ с вершиной S и основанием PQ равнобедренный тогда и только тогда, когда угол P равен углу Q " является истинной, так как высказывания " Треугольник SPQ с вершиной S и основанием PQ равнобедренный" и " В треугольнике SPQ с вершиной S и основанием PQ угол P равен углу Q " либо одновременно истинны, либо одновременно ложны.  
   
 
 25.
  
Эквивалентность играет важную роль в математических доказательствах. Известно, что значительное число теорем формулируется в форме необходимых и достаточных условий, то есть в форме эквивалентности. В этом случае, зная об истинности или ложности одного из двух членов эквивалентности и доказав истинность самой эквивалентности, мы заключаем об истинности или ложности второго члена эквивалентности.  
   
 
 26.
  
Итак, мы дали определения элементарных логических операций. Они позволяют строить сложные (составные) высказывания на основе заданных высказываний.  
   
 
 
  
Пусть x 1, x 2, x 3, x 4 - переменные высказывания (логические переменные), тогда следующие высказывания:  
   
 
 
  
,
   
 
 
  
представляют формулы алгебры высказываний. 		   
 
 27.
  
Так же, как и в алгебре арифметики, в алгебре логики устанавливается приоритет выполнения логических операций. Они упорядочены в следующей последовательности: 		   
 
 
  
,
   
 
 
  
При этом отрицание является наиболее сильной операцией, эквивалентность - самой слабой. С учетом указанного порядка две формулы: 		   
 
 
  
   
 
 
  
и
   
 
 
  
имеют одинаковые значения. 		   
 
 28.
  
Истинность составных высказываний (логических формул), образованных в результате выполнения логических операций над простыми высказываниями, зависит от истинности исходных высказываний. Для того, чтобы иметь возможность вычислять значения истинности этих высказываний, определим базовое понятие - логическую функцию. 		 
 
   

ЛОГИЧЕСКИЕ ФУНКЦИИ

 
 
 
 
 29.
  
Логической функцией называется функция f (x 1, x 1,...,x n) , которая, так же как и ее аргументы, может принимать только два значения (0 и 1). 		   
 
 30.
  
Совокупность значений аргументов будем называть набором . Каждому набору присваивается номер N , равный двоичному числу, образованному значениями аргументов на этом наборе. Условимся, что младшему разряду этого числа соответствует значение аргумента со старшим индексом, и наоборот. 		   
 
 
  
Итак: 		   
 
 
  
,
где n - общее число переменных. 		   
 
 
  
Например, пусть логическая функция зависит от трех переменных f(x1,x2,x3). Тогда набор x1=1, x2=1, x3=0 будет иметь номер 		   
 
 
  
.
   
 
 31.
  
Любую логическую функцию можно задать таблицей истинности, в левой части которой вписаны все возможные наборы значений ее аргументов x1,x2,...,xn , а правая часть - столбец значений функции, соответствующих этим наборам: 		   
 
 
  

№ набора

x1,x2,...,xn

f(x1,x2,...,xn)

0

Набор значений аргументов  

Значение функции

(0 или 1)

 

1

:

2n - 1
   
 
 
  
Число строк таблицы равно 2n (число всех возможных наборов из n аргументов). Число различных функций n переменных равно 2 в степени 2n - числу возможных расстановок нулей и единиц в столбце с 2n строками. 		   
 
 32.
  
Пусть n = 1. Таблица f(x) содержит две строки, а самих функций - четыре. 		   
 
 
  

№ набора

x

f(x)

№ набора

x

f(x)

0

0

0

0

0

0

1

1

0

1

1

1

 

Константа 0

f(x)=0

 

Повторение

f(x)=x

№ набора

x

f(x)

№ набора

x

f(x)

0

0

1

0

0

1

1

1

0

1

1

1

Отрицание f(x)=

Константа1 f(x)=1
   
 
 33.
  
Для n = 2 таких функций f(x1, x2) шестнадцать. Наиболее употребляемые из них: 		   
 
 
  

№
набopа

x1

x2

f(x1, x2)

№
набopа

x1

x2

f(x1, x2)

0

0

0

0

0

0

0

0

1

0

1

1

1

0

1

0

2

1

0

1

2

1

0

0

3

1

1

1

3

1

1

1

Дизъюнкция

Конъюнкция
   
 
 
  

№
набopа

x1

x2

f(x1, x2)

№
набopа

x1

x2

f(x1, x2)

0

0

0

1

0

0

0

1

1

0

1

1

1

0

1

0

2

1

0

1

2

1

0

0

3

1

1

0

3

1

1

0

 

Штрих Шеффера

("И - НЕ")

 

Стрелка Пирса

("ИЛИ - НЕ")
   
 
 
  

№
набopа

x1

x2

f(x1, x2)

№
набopа

x1

x2

f(x1, x2)

0

0

0

1

0

0

0

1

1

0

1

1

1

0

1

0

2

1

0

0

2

1

0

0

3

1

1

1

3

1

1

1

Импликация

Эквивалентность (равнозначность)

или x1 -> x2,

или x1x2.
   
 
 34.
  
Числовой способ задания логической функции. Логическую функцию от n аргументов будем еще обозначать символом f n . Если к тому же известно, что она равна 1 на наборах с номерами a i, i = 0,1,...,2 n-1 , то будем записывать это в виде: 		   
 
 
  
.
   
 
 
  
Например, для функции "Штрих Шеффера" . 		   
 
 35.
  
Если известно, что f n равна 0 на наборах с номерами b i, i = 0,1,...,2 n-1 , то будем записывать это в виде: 		   
 
 
  
.
   
 
 
  
Например, для " Стрелки Пирса " . 		   
 
 36.
  
Аргументы (переменные) и булевы функции с определенными на них элементарными операциями "отрицание", "конъюнкция" и "дизъюнкция" образуют алгебру Буля (булеву алгебру). 		   
 
 37.
  
В этой алгебре справедливы следующие основные соотношения, тождества, правила и законы. 		   
 
 
  

0 · 0 = 0,

0  0 = 0,

0 · 1 = 0,

0  1 = 0,

1 · 0 = 0,

1  0 = 0,

,

1 · 1 = 1,

1  1 = 1,

.
   
 
 
  
   
 
 
  

x · 0 = 0,

x  0 = 0

x · 1 = 1,

x  1 = 1

,

x ·  x · ...·  x ,

,

.
   
 
 
  
   
 
 
  
а) правило де Моргана:  
 
 
 
 б) конъюнктивное поглощение (x 1 поглощает x 1 x 2):  
 
  
 
в) дизъюнктивное поглощение (x 1 поглощает x 1· x 2);  
 
 
 
г) конъюнктивное склеивание по x 2:  
 
 
 
д) дизъюнктивное склеивание по x 2:  
 
;
 
 
е) конъюнктивное развертывание по x 2:  
 
;
 
 
ж) дизъюнктивное развертывание по x 2:  
 
.
 
 
 
 
а) ассоциативность дизъюнкции и конъюнкции:  
 
,
 
б) коммутативность дизъюнкции и конъюнкции:  
 

 
в) дистрибутивность конъюнкции относительно дизъюнкции:  
 
;
 
г) дистрибутивность дизъюнкции относительно конъюнкции:  
.
 
 
 
   

ВЫЧИСЛЕНИЕ ЛОГИЧЕСКИХ ФУНКЦИЙ

 
 
 
 
 38.
  
Если задана булева функция в виде формулы, то можно построить таблицу истинности, вычисляя ее значения на каждом из наборов.  
 
Пример 4.  
 
Дана булева функция Необходимо построить ее таблицу истинности.  
Решение.  
Функция трех переменных имеет всего восемь значений. Каждое получается на соответствующем наборе, начиная с набора  
0,0,0 (x1 = 0, x2 = 0, x3 = 0),  
кончая набором  
1,1,1 (x1 = 1, x2 = 1, x3 = 1).  
При вычислении пользуемся соотношениями:  
 
 
 
Результаты сведем в таблицу:  
 

№ набора

x1

x2

x3

f(x1, x2, x3)

0

0

0

0

0

1

0

0

1

1

2

0

1

0

0

3

0

1

1

0

4

1

0

0

1

5

1

0

1

1

6

1

1

0

0

7

1

1

1

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

АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ БУЛЕВЫХ ФУНКЦИЙ

 
 
 
 
 40.
  
Конституенты единицы . Булеву функцию, равную 1 только на одном наборе аргументов, называют конституентой единицы . Будем обозначать конституенту единицы, зависящую от n аргументов, символом: , где N - номер конституенты, равный номеру набора, на котором она равна 1. 		   
 
 41.
  
записывают в виде конъюнкции всех аргументов, взятых с отрицаниями или без них, по правилу: отрицания ставятся над аргументами, которые на наборе с номером N равны 0. 		   
 
 
  
Пример 5.  
 
Перечислить конституенты 1 функции, представленной таблицей истинности примера 4.  
Решение. 		   
 
 
  
.
   
 
 42.
  
Конституенты нуля . Булеву функцию, равную 0 только на одном наборе аргументов, называют конституентой нуля. Будем обозначать конституенту нуля, зависящую от n аргументов, символом , где N - номер конституенты, равный номеру набора, на котором она равна 0.  
 
 
 43.
  
записывают в виде дизъюнкции всех аргументов, взятых с отрицаниями или без них по правилу: отрицания ставятся над аргументами, которые на наборе с номером N равны 1.  
Пример 6.  
Перечислить конституенты 0 логической функции, заданной в примере 4.  
Решение. 		   
 
 
  
   
 
 44.
  
Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы булевой функции .  
Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы (СДНФ и СКНФ) относятся к числу канонических форм представления функций. Любая булева функция представима в СДНФ (кроме константы 0) и СКНФ (кроме константы 1). Запись произвольной булевой функции в этих формах проста и удобна для последующих преобразований. СДНФ и СКНФ у каждой функции единственны.  
   
 
 45.
  
СДНФ функции есть дизъюнкция всех ее конституент единицы.  
Пример 7.  
Записать в СДНФ булеву функцию, заданную таблицей примера 4. Решение.  
Конституенты 1 этой функции представлены в примере 5. Объединим их знаком дизъюнкции:  
. 		   
 
 46.
  
СКНФ функции есть конъюнкция всех ее конституент нуля.  
Пример 8.  
Записать в СКНФ булеву функцию из примера 4.  
Решение.  
 
 
 
 
   

МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ

 
 
 
 
 47.
  
Задача минимизации булевой функции сводится к такому представлению функции, которое содержит наименьшее возможное число букв и наименьшее возможное число операций над ними. Выделим два подхода к решению поставленной задачи: алгебраический подход и графический подход.  
   
 
 48.
  
. Алгебраический подход. Минимизация как упрощение формул в булевой алгебре (как и в любой другой алгебре) производится на основе эквивалентных преобразований , опирающихся на основные законы, тождества и правила, о которых речь шла выше.  
Пример 9.  
Показать, что f1(x,y)=f2(x,y), где , а .  
Решение.  
Умножим (логически) f2(x, y) на - логическую единицу:  
 
Воспользуемся тождествами , правилом дизъюнктивного поглощения . Окончательно получим:  
 
Пример 10. Упростить логическую функцию  
 
 
Решение.  
Раскроем скобки, выполнив логическое умножение. В результате получим:  
 
 
 
 
 
Пример 11.  
Упростить булеву функцию  
Решение.  
Учитывая, что , получим:
 
 
Пример 12.  
 Упростить логическую функцию  
 
Решение. Учитывая, что , получим:  
 
Используя соотношение (смотри пример 9), получим:
Тогда:  
 
Для выражения в круглых скобках воспользуемся правилом де Моргана  
 
Следовательно,  
Воспользуемся опять соотношением  
 
Окончательно получаем:  
 
   
 
 49.
  
Окончательное (упрощенное) выражение отличается от искомого уменьшенным количеством букв в выражении. Однако часто требуется показать эквивалентность исходной и упрощенных форм. Обе функции должны иметь одну и ту же таблицу истинности. Построим такие таблицы для исходной и упрощенной функции последнего примера.  
 

№ набора

x1x2x3x4

 

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

0 0 0 0

0 0 0 1

0 0 1 0

0 0 1 1

0 1 0 0

0 1 0 1

0 1 1 0

0 1 1 1

1 0 0 0

1 0 0 1

1 0 1 0

1 0 1 1

1 1 0 0

1 1 0 1

1 1 1 0

1 1 1 1

 

0

1

1

1

0

1

1

1

1

1

1

1

0

1

1

1

0

1

1

1

0

1

1

1

1

1

1

1

0

1

1

1
 
Видно, что таблицы истинности идентичны.  
Замечание.  
 Упрощать эквивалентными преобразованиями можно любое логическое выражение (если такие преобразования возможны). Минимизировать (для получения минимальной формы) можно только каноническую форму - СДНФ или СКНФ, то есть корректно логическое выражение свести к канонической форме, а затем минимизировать. 		   
 
 50.
  
Графический подход.  
 Минимизацию удобно проводить с использованием карт Карно . Карта Карно (диаграмма Вейча) представляет собой своеобразный способ задания булевых функций при помощи специальной таблицы, число клеток которой равно числу всех возможных наборов аргументов булевой функции.  
Для функции, заданной в СДНФ, нужно в клетки, соответствующие дизъюнктивным членам, записать единицы. Для карты Карно любая пара склеивающихся между собой конституент единицы располагается в соседних, вертикально и горизонтально расположенных клетках.  
   
 
 51.
  
Карта Карно функции трех переменных f(x1,x2,x3):  
 
Здесь соседними клетками являются также клетки, расположенные в первой и последней колонках, т.е. карту Карно для функции трех переменных рассматривают как развертку боковой поверхности цилиндра. Для этой карты возможно склеивание по два или четыре члена, что будет соответствовать конъюнкции двух или одной переменной. Процесс отыскания минимальной (упрощенной) функции будет заключаться в том, чтобы всю совокупность единиц карты Карно накрыть наименьшим числом наиболее коротких произведений (крупных контуров).  
 
Пример 13.  
Минимизировать f(x1,x2,x3) , заданную ее СДНФ (пример 7) с помощью карты Карно.  
 
Решение.  
 
Карта Карно функции:  
 
 
Итак:  
   
 
 52.
  
Приведем карту Карно для булевой функции четырех переменных.  
 
 
 
Для этой диаграммы соседними считаются также клетки, расположенные в нижних и верхних строках. Для этой карты возможно склеивание по два, четыре или восемь членов.  
Пример 14.  
Упростить логическую функцию  
 
Решение.  
Перечислим конституенты 1 данной функции:  
 
 
 
Составим карту Карно для этой функции:  
 
 
 
Окончательно:  
 
.
 
 
 
   

АЛГОРИТМЫ РЕШЕНИЯ ЛОГИЧЕСКИХ ЗАДАЧ

 
 
 
 
 53.
  
Решить логическую задачу - значит, найти истинное высказывание, отвечающее на поставленный в задаче вопрос. Необходимо подчеркнуть, что в качестве данных и в качестве разыскиваемой величины выступают высказывания, которые при решении алгебраических задач обозначаются символами.  
   
 
 54.
  
Последовательность решения логической задачи:  
а) обозначение символами исходных и разыскиваемых высказываний;  
б) составление логических выражений (сложных высказываний) для всех требований задачи с использованием логических связок (элементарных логических операций);  
в) вычисление значений полученного выражения при всех возможных комбинациях истинности и ложности исходных высказываний или преобразование сложного выражения к виду, который однозначно дает ответ;  
г) проверка полученного решения по условию задачи.  
 
Пример 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 веке" (Борис).  
Рассуждая аналогично, получим:  
 
 
Высказывание Валерия определяет логическое равенство:  
 
 
Итак, имеем систему уравнений:  
 
 
 
Порассуждаем логически. Сосуд может быть изготовлен только в одной стране, то есть x1 = 0.  
Сосуд может быть изготовлен только в одном веке:  
 
 
 
Сведем три истинных высказывания системы в одно. Чтобы новое высказывание было истинным при истинных составляющих его высказываниях, их надо логически перемножить:
 
 
Таким образом, решить задачу - значит указать, при каких значениях х1, х2, х3, х4, х5 сложное высказывание Х истинно.  
 
Найти набор, при котором Х = 1 можно, вычисляя значения Х на всех возможных наборах, заполняя таблицу истинности.  
 
Видно, что набор N=12 единственный, при котором Х=1 . Комбинация истинных высказываний: сосуд финикийский ( х2=1) и изготовлен в V веке ( х3=1).  
 

№ набора

х1х2х3х4х5

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

0 0 0 0 0

0 0 0 0 1

0 0 0 1 0

0 0 0 1 1

0 0 1 0 0

0 0 1 0 1

0 0 1 1 0

0 0 1 1 1

0 1 0 0 0

0 1 0 0 1

0 1 0 1 0

0 1 0 1 1

0 1 1 0 0

0 1 1 0 1

0 1 1 1 0

0 1 1 1 1

1 0 0 0 0

1 0 0 0 1

1 0 0 1 0

1 0 0 1 1

1 0 1 0 0

1 0 1 0 1

1 0 1 1 0

1 0 1 1 1

1 1 0 0 0

1 1 0 0 1

1 1 0 1 0

1 1 0 1 1

1 1 1 0 0

1 1 1 0 1

1 1 1 1 0

1 1 1 1 1

0

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0
 
Другой способ решения этой задачи заключается в упрощении функции Х(х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, то есть убийца - Этьен.  
 
 
 
 
   

КРАТКО О ГЛАВНОМ

 
 
 
 
 1.
  
Основной объект изучения логики - элементарные высказывания. Из них с помощью логических связок (элементарных операций) строятся сложные высказывания.  
   
 
 2.
  
При алгебраическом подходе эти высказывания рассматриваются как формулы, которые можно вычислять и преобразовывать. Логическими переменными обозначают элементарные высказывания. Формулы определяют логические функции.  
   
 
 3.
  
Логические функции, переменные, элементарные операции образуют алгебру Буля (булеву алгебру). Для булевой алгебры справедливы определенные соотношения, тождества, правила и законы.  
   
 
 4.
  
Булева функция - функция, как и ее аргументы принимающая только два значения: 0 и 1. Совокупность значений аргументов называется набором. Всего может быть 2N наборов аргументов.  
   
 
 5.
  
Функция может быть задана таблично (таблица истинности), числовым способом, аналитически (в виде СДНФ или СКНФ), графически (картой Карно).  
   
 
 6.
  
Цель минимизации - упрощение СДНФ (СКНФ), чтобы в минимальной форме было наименьшее возможное число букв и наименьшее возможное число знаков операций. Существует два подхода к минимизации: алгебраический (преобразование формул) и графический (поиск контуров на карте Карно).  
   
 
 7.
  
Чтобы решить логическую задачу, необходимо найти истинное высказывание, отвечающее на поставленный в задаче вопрос.