1.5. Представление произвольной двузначной функции посредством формулы алгебры высказываний.

Описание алгебры высказываний имеет и функциональный подход; любая логическая формула α(А,В,С…) задает некоторую функцию, определенную на множестве высказываний со значением в нем же.

n=1, F₁={y=f(x)};

f₀(x)=xΛ¬x,

f₁(x)=xV¬x,

f₂(x)=x,

f₃(x)=¬x.

x	f0(x)	f1(x)	f2(x)	f3(x)
И	Л	И	И	Л
Л	Л	И	Л	И

Y=F(x₁, x₂,…, x_n), nN – двухзначная n-местная функция.

Теорема 1:

Пусть │f_n│ - число различных n-местных булевых функций. Тогда │f_n│= .

Логические функции могут быть заданы:

1. описательно;

2. таблично;

3. в виде логической формулы;

4. в виде электрической схемы.

Теорема 2:

Любая n-местная двухзначная функция F(x₁, x₂,…, x_n) представима в виде логической формулы, составленной из переменных или их отрицаний в ДНФ.

Для того чтобы получить ДНФ для f_i достаточно выделить те строчки, в которых f_i=И. С любой выделенной строчкой связывается логическое произведение переменных. В это логическое произведение войдет сам аргумент если принимает значение истина, а если принимает ложь, то его отрицание.

Можно переходить от описательного задания к табличному, от табличного к аналитическому, и от аналитического к табличному.

Замечание:

Как и в любой алгебре, вынесение за скобки ведет к сокращению.

Релейно-контактные схемы:

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

И – включено «ток проходит»;

Л – выключено «ток не проходит»;

X – замыкающий контакт;

¬X – размыкающий контакт;

Λ – последовательное соединение;

V – параллельное соединение.

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

1.6. Совершенные нормальные формы.

Определение:

Совершенной ДНФ формулы α(x₁, x₂,…, x_n) называется ДНФ, обладающая следующими свойствами:

а) в ней нет двух одинаковых слагаемых;

б) ни одно слагаемое не содержит двух одинаковых множителей;

в) никакое слагаемое не содержит переменной вместе с ее отрицанием;

г) в каждом слагаемом содержится в качестве множителя либо переменная x_i, либо ее отрицание.

Перечисленные условия ведут к следующим правилам приведения к СДНФ:

1. привести α к какой-нибудь ДНФ, и если одно из слагаемых β не имеет переменной x_i, то заменить слагаемое β суммой: x_iβV¬x_iβ;

2. если в полученном выражении окажутся одинаковые слагаемые, то удалить все кроме одного;

3. если в слагаемых окажется несколько одинаковых множителей, то удалить все кроме одного;

4. удалить все те слагаемые, которые содержат какую-нибудь переменную вместе с ее отрицанием.

Определение:

Совершенной конъюнктивной нормальной формой формулы α(x₁, x₂,…, x_n) называется ее КНФ, удовлетворяющая условиям:

а*) в ней нет двух одинаковых множителей;

б*) ни один множитель не содержит двух одинаковых слагаемых;

в*) ни один множитель не содержит какой-нибудь переменной вместе с ее отрицанием;

г*) каждый множитель содержит в качестве слагаемого либо переменная x_i, либо ее отрицание.

Правила для СКНФ те же, но выражаются в двойственных терминах.