Вопросы к зачету часть1 (Вопросы к зачету (ответы)), страница 3

Среди функции от 2 аргументов также выделим некоторые функции (табл. 1.3). Они носят соответственно Таблица 1.3.

названия конъюнкции, дизъюнкции, импликации, суммы по модулю 2 (по mod 2) и эквивалентности. Как

можно видеть из таблицы, конъюнкция равна 1 лишь в случае, когда оба аргумента обращаются в 1, а дизъюнкция равна 0 лишь на нулевом наборе. Конъюнкцию принято также называть логическим умножением а дизъюнкцию — логическим сложением. Импликация обращается в 0 только в случае, когда значение второго аргумента меньше значения первого аргумента. Функция эквивалентности равна 1 при совпадении значений аргументов, а функция суммы по модулю 2—при несовпадении. Название последней из этих функций объясняется тем, что она принимает значение 1 на наборах с нечетным числом единиц и значение и 0—на наборах с четным числом. Перечисленные функции от одного и двух аргументов будем называть элементарными.

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

Пусть имеется некоторое множество В логических функции. Множество В будем называть базисом, а входящие в него функции—базисными. По индукции определим понятие формулы (над В):

—выражение f(x₁, ..., х_n), где f—базисная функция, есть формула;

—если f_o(x₁, ..., х_m) базисная функций, а выражения Ф₁ ..., Ф_m являются либо формулами, либо символами переменных, то выражение f( Ф₁ ..., Ф_m) есть формула.

Все формулы, которые встречались в процессе построения заданной формулы, будем называть ее под формулами. В качестве примера рассмотрим базис B={g( x_1,x₂), h(x_1,x_2, x₃)), состоящий из двух функций Выражение h(g(x_1,h(x_1,x_2, x₃), x₁), h(x_1,x_2, x₃), x₁)) является формулой над B. Под формулами здесь будут

g( x_1,x₂), h(x_1, g( x_1,x₂),x₁), h(x_2,x_2,x₂), g(x₁,h(x_2,x_2, x₂)) и вся формула.

Каждой формуле следующим образом, сопоставляется реализуемая ей логическая функция:

—формуле вида f(x₁, ..., х_n), где f—базисная функция, ставится в соответствие функция f(x₁, ..., х_n),;

— если формула имеет вид f_o(x₁, ..., х_m), где Ф_i (i=1,..,m) является либо формулой, либо символом переменной x_j, то ей сопоставляется функция f(f₁, ..., f_m) где f_i является соответственно либо функцией, реализуемой под формулой Ф_i, либо тождественной функцией x_j(i).

Функция, реализуемая формулой, зависит от переменных, которые участвовали в ее построении. В качестве примера рассмотрим формулу (x₂> x₁)&((( x₂ 1)& )~ ). Она реализует некоторую функцию f(x₁, x₂,x₃). Пользуясь таблицами для элементарных функций, можно вычислить ее значение на любом наборе (₁, ₂, ₃). Проделаем это для набора (0,1,0):

(1 0) & ((( 1 1 )& ) ~ )= (1  0) & ((0 & 1) ~ 1) = 0 & (0 ~ 1) = 0 & 0 = 0.

Подобным образом можно убедиться, что функция f(x₁, x₂, x₃), задается таблицей 1.1.

1.1.3. Эквивалентные преобразования формул. Формулы Ф и Ψ будем называть эквивалентными и записывать Ф =Ψ,если они реализуют равные функции, т.е. на одинаковых наборах принимают одинаковые значения. Эквивалентность формул может быть установлена путем нахождения табличного задания реализуемых ими функций и сравнения этих таблиц (другой способ проверки эквивалентности будет изложен в следующем параграфе). Очевидно, что замена в формуле некоторой подформулы на эквивалентную дает формулу, эквивалентную исходной. На основании этого можно осуществлять преобразования формул, не изменяющие реализуемых функций.

Дальше в пределах параграфа будем рассматривать формулы над базисом B_o={0,1, ,–,&,V, >, , ~}, состоящим из всех элементарных функций.

По таблицам 1.2 и 1.3 легко проверить, что имеют место эквивалентности

, (1.1)

=( & ) \/ ( & ), (1.2)

~ =( & )\/ ( & ). (1.3)

С их использованием формулы над В могут быть заменены эквивалентными формулами над более узким базисом {0,1, , –,&, }

Приведем некоторые важные эквивалентности для базиса {0, 1, , –,&, }:

( & )& = &( & ), свойства ассоциативности,

( \/ )\/ = \/( \/ )

& ₌ & свойства коммутативности,

\/ ₌ \/ ,

& = свойства идемпотентности,

\/ ₌

&( \/ )= ( & ) \/ ( & ) свойства дистрибутивности

( & )= ( \/ ) & ( \/ )

=

законы де Моргана,

Кроме того, справедливы следующие соотношения с участием констант:

&0=0, &1= , & =0,

1=1, 0= , = 1

Из свойства ассоциативности следует, что можно рассматривать многоместную конъюнкцию

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

n =1 и n=0. В случае n= 1 они означают x. Пустая конъюнкция (при n=0) полагается равной 1, пустая дизъюнкция— равной 0. Законы де Моргана могут быть обобщены для произвольного n:

,

При n>2 в этом можно убедиться, представив многоместную функцию с помощью двухместных. При n=3, например, цепочка преобразований имеет вид

( )=

В случае n=0 и n=1 соотношения (1.4) выполняются очевидным образом.

Соотношения (1.4) допускают дальнейшее обобщение. Пусть функция f реализуется некоторой формулой в базисе {0,1,-,&, }. Тогда формула, реализующая ее отрицание f, может быть получена по следующему правилу. Все функции & должны быть заменены на , функции —на &, переменные , должны быть заменены их отрицаниями, а константы 0 и 1 — противоположными константами 1 и 0. Это вытекает из законов де Моргана, на основе которых отрицание над формулой может быть последовательно пронесено вглубь формулы, пока оно не перейдет на переменные и константы.

Для пояснения этого рассмотрим пример. Пусть функция f задается формулой

f= (( & ) ) & Последовательное применение законов де Моргана дает

Тот же результат получается с использованием указанного правила.

1.1.4. Упрощение формул. В дальнейшем с целью сокращения записей условимся знак & иногда заменять точкой или опускать и считать, что операция & связывает сильнеее других операций, т. е. что она выполняется раньше их (если скобки не предписывают другого порядка). Так, вместо записи будем применять .

Укажем некоторые полезные эквивалентности, которые могут быть использованы для упрощения формул:

\/ = правила поглощения,

( \/ ) =

\/ = — правило склеивания,

\/ = \/ — правило вычеркивания.

Их доказательства проводятся на основе эквивалентностей, приведенных раньше:

При применении указанных правил вместо переменных x₁ и x₂ могут подставляться любые формулы.

Применение правил проиллюстрируем на примере ранее рассматривавшейся формулы

Используя соотношения (1.1)—(1.3), осуществим ее перевод в базис {0, 1,x,~,&, \/} с одновременным упрощением. Имеем

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

8. Доказательство теоремы о разложении логической функции по К переменным.

Разложение по переменным. Пусть x—логическая переменная. При {0,1} введем обозначение

при , при

Легко проверить, что х = 1 тогда и только тогда, когда х = . Следовательно, конъюнкция равна 1 на единственном наборе значений аргументов

Следующая теорема позволяет выразить функцию f(x₁, ..., x_n) через функции от меньшего числа аргументов.

Т е о р е м а 1.1 (о разложении функций). Всякая логическая функция f(x₁, ..., x_n) при любом k (1?k?n) может быть представлена в виде