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

Пусть F(x₁,x_2,..., х_п) - произвольная функция алгеб­ры логики п переменных. Рассмотрим формулу

F (1,1,...1) &x₁&x₂&...&x_n

F (1,1,...,1,0)& x₁&х₂&...&x_n-1& _n

F (l,l,…,0,l)& x ₁& х₂ &… &...&x_n-2& _n-1&x_n …

F (0,0,...,0) & ₁& ₂&...& _n

которая составлена следующим образом: каждое слагае­мое этой логической суммы представляет собой конъюн­кцию, в которой первый член является значением функ­ции F при некоторых определенных значениях перемен­ных х₁, х₂,..., х_п , остальные же члены конъюнкции пред­ставляют собой переменные или их отрицания. При этом под знаком отрицания находятся те итолько те пере­менные, которые в первом члене конъюнкции имеют зна­чение 0.

Вместе с тем формула (1) содержит в виде логичес­ких слагаемых всевозможные конъюнкции указанного вида.

Ясно, что формула (1) полностью определяет функ­цию F(x₁,x₂,...,x_n). Иначе говоря, значения функции F и формулы (1) совпадают на всех наборах значений пере­менных x₁,x₂,...,x_n.

Например, если х₁ принимает значение 0, а осталь­ные переменные принимают значение 1, то функция F принимает значение F (0,1,1,...1). При этом логическое слагаемое F (0,1,1,...1)& ₁& x ₂ &...&х_п, входящее в форму­лу (1), принимает также значение F (0,1,...1), все ос­тальные логические слагаемые формулы (1) имеют зна­чение 0. Действительно, вних знаки отрицания над переменными распределяются иначе, чем в рассмотрен­ном слагаемом, но тогда при замене переменных теми же значениями в конъюнкцию войдет символ 0 без знака от­рицания, символ 1 под знаком отрицания. В таком слу­чае один из членов конъюнкции имеет значение 0, а по­этому вся конъюнкция имеет значение 0. В связи с этим на основании равносильности x 0 x значением фор­мулы (1) является F (0,1.....l).

Ясно, что вид формулы (1) может быть значительно упрощен, если в ней отбросить те логические слагаемые, в которых первый член конъюнкции имеет значение 0 (и, следовательно, вся конъюнкция имеет значение 0). Если же в логическом слагаемом первый член конъюнк­ции имеет значение 1, то, пользуясь равносильностью 1& х х, этот член конъюнкции можно не выписывать.

Таким образом, в результате получается формула (1), которая содержит только элементарные переменные выс­казывания и обладает следующими свойствами:

1) Каждое логическое слагаемое формулы содержит

все переменные, входящие в функцию F(x₁,x₂,...,x_n).

2) Все логические слагаемые формулы различны.

3) Ни одно логическое слагаемое формулы не содер­жит одновременно переменную и ее отрицание.

4) Ни одно логическое слагаемое формулы не содер­жит одну и ту же переменную дважды.

Перечисленные свойства будем называть свойства­ми совершенства или, коротко, свойствами (С).

Из приведенных рассуждений видно, что каждой не тождественно ложной функции соответствует единствен­ная формула указанного вида.

Если функция F(x₁,x₂,...,x_n) задана таблицей ис­тинности, то соответствующая ей формула алгебры ло­гики может быть получена просто. Действительно, для каждого набора значений переменных, на котором фун­кция F(x₁,x₂,...,x_n) принимает значение 1, запишем конъюнкцию элементарных переменных высказываний, взяв за член конъюнкции x_k, если значение x_k на ука­занном наборе значений переменных есть 1 и отрицание x_k, если значение x_k есть 0. Дизъюнкция всех записан­ных конъюнкций и будет искомой формулой.

Пусть, например, функция F(x₁,x_2, x₃) имеет следу­ющую таблицу истинности:

x1	x2	x3	F(x1,x2, x3)

Для наборов значений переменных (1,1,0), (l,0,l), (0,l,0), (0,0,0), на которых функция принимает значение 1, запишем конъюнкции х₁&х₂& ₃, х₁& ₂&х₃, ₁&х₂& ₃, ₁& ₂& ₃, а искомая формула, обладающая свойствами (С), имеет вид:

х₁&х₂& ₃ х₁& ₂&х_{3 1}&х₂& ₁& ₂& ₃

Закон двойственности

Пусть формула А содержит только операции конъ­юнкции, дизъюнкции и отрицания.

Будем называть операцию конъюнкции двойствен­ной операции дизъюнкции, а операцию дизъюнкции двойственной операции конъюнкции.

Определение. Формулы А и А* называются двой­ственными, если формула А* получается из формулы А путем замены в ней каждой операции на двойственную.

Например, для формулы A (x y)&z двойственной формулой будет формула А* (х&у) z.

Теорема. Если формулы А и В равносильны, то равносильны и им двойственные формулы, то есть А* В*.

Предварительно докажем лемму.

Лемма. Если для формулы А(х₁,х₂,...х_п) двойствен­ной формулой является А *(х₁,х₂,...х_п), то справедлива равносильность

A*( ₁, ₂,... _п).

Доказательство. Для элементарной формулы утвер­ждение леммы очевидно. Действительно, если A(x₁) x₁,

то A*(x₁) x₁, (x₁) , А*( ) и .

Пусть теперь утверждение леммы справедливо для всяких формул, содержащих не более k операций. Дока­жем, что при этом предположении утверждение справед­ливо и для формулы, содержащей k + 1 операцию.

Пусть формула A(x₁,x₂,...x_n) содержит k + 1 опера­цию. Тогда ее можно представить в одном из трех видов:

1) А(х₁,х₂,...х_п) ,

2) А(х₁,х₂,...х_п) А₁(х₁,х₂,...х_п) А₂(х₁,х₂,...х_п),

3) А(х₁,х₂,...х_п) А₁(х₁,х₂,...х_п) & А₂(х₁,х₂,...х_п),

где формулы А₁(х₁,х₂,...х_п) и А₂(х₁,х₂,...х_п) содержат не более k операций, и, следовательно, для них утверж­дение справедливо, то есть

( ₁, ₂,… _п),

( ₁, ₂,… _п).

В случае 1) имеем А* а поэтому

В случае 2) имеем , апоэтому

Аналогичное доказательство проводится и в случае 3). Докажем теперь закон двойственности.

Пусть формулы А(х₁,х₂,...х_п) и B(х₁,х₂,...х_п) равно­сильны:

А(х₁,х₂,...х_п) B(х₁,х₂,...х_п).

Но тогда, очевидно,

В то же время, согласно лемме,

 

 

Из равносильностей (1) и(2) получаем

,

и, следовательно,

А^*(х₁,х₂,...х_п) и B^*(х₁,х₂,...х_п)