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

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

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

f₀(x)=xΛx,

f₁(x)=xVx,

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 – параллельное соединение.

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

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