Реализация конечного автомата системой булевых функций

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

Основу теории булевых функций составляет понятие «Высказывание». Высказывание – это некое утверждение, о котором можно говорить, что оно истинно или ложно. Например, высказывание «Москва – столица России» является истинным, а высказывание «15>24» является ложным. Таким образом, высказывание обладает свойством представлять истину или ложь, поэтому на высказывание можно смотреть как на величину, которая принимает только одно из двух значений: «истина» и «ложь». Сопоставим в соответствии высказыванию логическую переменную x, которая принимает значение 1 “true”, если высказывание истинно, и 0 “false”, если высказывание ложно. Внутренняя структура высказывания не представляет интереса и имеет отношение к лингвистике. Мы будем поступать так, как если бы мы знали все о простых высказываниях. Эти высказывания будем называть элементарными. Элементарное высказывание – это одно утверждение. Высказывание, которое строится из множества элементарных высказываний, называется составным высказыванием. Составные высказывания получаются из элементарных с помощью следующих логических операций:

Отрицание (не)

Отрицанием высказывания x называется высказывание , которое истинно, когда x ложно, и ложно, когда x истинно. Таблица истинности для отрицания

x
0	1
1	0

Конъюнкция (и)

Конъюнкцией двух высказываний x и y называется высказывание x˄y, которое истинно только в том случае, когда x и y оба истинны. Таблица истинности для конъюнкции

x	y	x˄y
0	0	0
0	1	0
1	0	0
1	1	1

Дизъюнкция (или)

Дизъюнкцией двух высказываний x и y называется высказывание x˅y, которое истинно, когда хотя бы одно из них истинно. Таблица истинности для дизъюнкции

x	y	x˅y
0	0	0
0	1	1
1	0	1
1	1	1

Импликация (если … то)

Импликацией двух высказываний x и y называется высказывание x→y, которое ложно тогда и только тогда, когда x истинно, а y ложно. Таблица истинности для импликации

x	y	x→y
0	0	1
0	1	1
1	0	0
1	1	1

Эквивалентность (тогда и только тогда, когда)

Эквивалентностью двух высказываний x и y называется высказывание x↔y, которое истинно тогда и только тогда, когда x и y оба истинны или ложны. Таблица истинности для эквивалентности

x	y	x↔y
0	0	1
0	1	0
1	0	0
1	1	1

С помощью введенных операций можно строить различные составные высказывания. Порядок выполнения операций указывается скобками. Если скобок нет, то операции выполняются в следующем порядке: конъюнкция ˄, дизъюнкция ˅, импликация →, эквивалентность ↔, отрицание. Для каждого составного высказывания можно построить свою таблицу истинности.

Логические отношения

Иногда бывает желательно рассмотреть взаимоотношение двух высказываний. Наиболее интересное отношение такого рода имеет место, когда из одного высказывания логически следует другое. Если из x следует y, мы говорим также, что y является следствием x или что y логически выводимо из x. Исходя из анализа логических возможностей для пары высказываний x и y, отношение следствия можно охарактеризовать таким образом: из x следует y, если y истинно всякий раз, когда истинно x, т. е. если y истинно во всех логически возможных случаях, в которых x истинно.

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

Следующая таблица иллюстрирует этот метод:

x	y	x↔y	x→y	x˅y
0	0	1	1	0
0	1	0	1	1
1	0	0	0	1
1	1	1	1	1

Высказывание x↔y истинно в первом и четвертом случаях и в обоих этих случаях истинно также высказывание x→y. Мы видим, что из x↔y следует высказывание x→y. Сравнение двух последних столбцов показывает, что из высказывания x→y не следует x˅y, из x˅y не следует x→y. При помощи таблиц истинности удобно осуществлять проверку эквивалентности двух составных высказываний, имеющих одни и те же компоненты. Для этого достаточно лишь посмотреть, одинаковы ли таблицы истинности у этих составных высказываний.

Из следующей таблицы истинности видно, что x→y эквивалентно ˅y.

x	y	x→y	˅y
0	0	1	1
0	1	1	1
1	0	0	0
1	1	1	1

Два высказывания называются логически несовместимыми, если из истинности одного из них необходимо следует ложность другого Другими словами, несовместимость высказываний x и y означает, что они никогда не могут оказаться одновременно истинными. Если несколько составных высказываний построены из одних и тех же простых составляющих, то для проверки их совместимости нужно построить таблицы истинности для каждого из высказываний. Если среди всех строк найдется, по крайней мере, одна, в которой все составные высказывания истинны, то составные высказывания совместимы. В противном случае они оказываются несовместимыми.

Импликация двух высказываний отличается от эквивалентности, а также от дизъюнкции и конъюнкции тем, что она несимметрична. Так x˅y эквивалентно y˅x; x˄y эквивалентно y˄x; x↔y эквивалентно y↔x, но x→y не эквивалентно y→x. Высказывание y→x называется конверсией высказывания x→y. Многие из наиболее распространенных ошибок в рассуждениях происходят от смешивания какого-либо высказывания с его конверсией. Интересно поэтому рассмотреть те импликации, которые могут быть образованы из высказываний x и y.

В таблице истинности представлены четыре импликации и их названия:

x	y			импликация x→y	конверсия импликации y→x	конверсия контрапозиции →	контрапозиция →
0	0	1	1	1	1	1	1
0	1	1	0	1	0	0	1
1	0	0	1	0	1	1	0
1	1	0	0	1	1	1	1

Из таблицы видно, что x→y эквивалентно →. С импликацией связано постоянное упоминание математиками «необходимое условие» и «достаточное условие».

x является достаточным условием для y	Если имеет место x, то y также будет иметь место	Импликация x→y
x является необходимым условием для y	Если имеет место y, то x также будет иметь место	конверсия импликации y→x
x является необходимым и достаточным условием для y	x имеет место, если и только если имеет место y	Двойная импликация x↔y эквивалентность

Пример:

Найти символическую форму и построить таблицу истинности для следующих высказываний:

1. Если Алиса умна, а Боб глуп, то Алиса решит задачу.

2. Алиса решит задачу в том и только в том случае, если она умна или если Боб глуп.

3. Если Боб глуп, а Алисе не удастся решить задачу, то Алиса не умна.

Введем буквенные обозначения: x для «Алиса умна»; y для «Боб глуп»; z для «Алиса решит задачу».

1. «Алиса умна» и «Боб глуп» символически записываются x˄y. Поскольку это условие является достаточным для высказывания z, то составное высказывание примет вид x˄y→z.

2. «Алиса умна» или «Боб глуп» можно записать как x˅y. Это условие является необходимым и достаточным для решения задачи Алисой, т.е. x˅y↔z.

3. «Боб глуп», а «Алиса не решит задачу» записывается как y˄. Соответственно составное высказывание имеет вид y˄→.

x	y	z	.		x˄y	x˄y→z	x˅y	x˅y↔z	y˄	y˄→
0	0	0	1	1	0	1	0	1	0	1
0	0	1	1	0	0	1	0	0	0	1
0	1	0	1	1	0	1	1	0	1	1
0	1	1	1	0	0	1	1	1	0	1
1	0	0	0	1	0	1	1	0	0	1
1	0	1	0	0	0	1	1	1	0	1
1	1	0	0	1	1	0	1	0	1	0
1	1	1	0	0	1	1	1	1	0	1

Булевы функции

Функцию f(x₁,x₂,…,x_n), принимающую одно из двух значений 0 (false) или 1 (true), от n переменных, каждая из которых принимает одно из двух значений 0 или 1, будем называть булевой функцией от n переменных. Булева функция от n переменных сопоставляет каждому упорядоченному набору (кортежу), составленному из n элементов, 0 и 1, либо 1, либо 0.

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

Булевых функций одной переменной четыре:

x	f1(x)	f2(x)	f3(x)	f4(x)
0	0	0	1	1
1	0	1	0	1

Функции f₁(x) и f₄(x) называют константами – соответственно 0 и 1. Функция f₂(x)совпадает с переменной x и называется тождественной f₂(x)=x. Функция f₃(x)= принимает значения, противоположные значениям аргумента и называется отрицанием.

Количество булевых функций двух переменных равно шестнадцати. Таблица истинности булевой функции двух переменных:

x1	x2	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15	f16
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Функции f₁(x₁,x₂) и f₁₆(x₁,x₂)представляют собой константы 0 и 1. Функции f₄, f₆ , f₁₁ и f₁₃ существенно зависят только от одной переменной: f₄(x₁,x₂)=x₁, f₆(x₁,x₂)=x₂, f₁₁(x₁,x₂)=, f₁₆(x₁,x₂)=. У остальных функций есть свои названия и обозначения:

f₂(x₁, x₂) = x₁˄x₂ конъюнкция

f₈(x₁, x₂) = x₁˅x₂ дизъюнкция

f₁₀(x₁, x₂) = x₁↔x₂ эквивалентность

f₇(x₁, x₂) = сумма по модулю два, или сумма Жегалкина

f₁₂(x₁, x₂) = x₂→x₁ конверсия

f₁₄(x₁, x₂) = x₁→x₂ импликация

f₁₅(x₁, x₂) = штрих Шеффера

f₉(x₁, x₂) = стрелка Пирса

f₇(x₁, x₂) = функция запрета

f₅(x₁, x₂) = функция запрета

Булеву функцию любого числа переменных можно задать формулой, содержащей функции одной и двух переменных посредством подстановки одних булевых функций вместо переменных в другие булевы функции, т.е. посредством суперпозиций булевых функций. Число булевых функций от n переменных равно .

Дизъюнктивные и конъюнктивные нормальные формы булевых функций.

Для любой булевой функции можно построить ее таблицу истинности. Но и по таблице истинности можно восстановить булеву функцию.

Конъюнктивным одночленом от переменных x₁,x₂,…,x_n называется конъюнкция этих переменных или их отрицаний.

Дизъюнктивным одночленом от переменных x₁,x₂,…,x_n называется дизъюнкция этих переменных или их отрицаний.

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

Например: (x₁˄x₂˄x₃) ˅(x₁˄) ˅( x₂˄x₃) ˅ – ДНФ

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

Например: (˅x₂˅x₃) ˄ (x₁˅) ˄x₃ – КНФ

Алгоритм построения

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

x₁→x₂ =˅x₂ ; x₁↔x₂=(˅x₂) ˄( x₁˅) ; x₁↔x₂=( x₁˄x₂) ˅(˄)

2. Заменить знак отрицания, относящийся к выражениям типа и , знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:

=˄ ; =

3. Избавиться от знаков двойного отрицания.

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

x₁˄(x₂˄x₃) ↔ (x₁˄x₂)˄x₃ , x₁˅ (x₂˅x₃) ↔ (x₁˅x₂) ˅x₃ – ассоциативность

x₁˅(x₂˄x₃)↔(x₁˅x₂)˄(x₁˅x₃), x₁˄(x₂˅x₃)↔(x₁˄x₂)˅(x₁˄x₃)– дистрибутивность

x₁˄x₂˅x₁= x₁ , x₁˄(x₁˅x₂)= x₁ – закон поглощения