Главная Случайная страница


Полезное:

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

Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






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





 

Пусть с помощью таблицы истинности задана произвольная функция алгебры логики n переменных F(x1, x2, …, xn). Рассмотрим формулу:

F(1, 1, …, 1) Ù x1 Ù x2 Ù … Ù xn Ú

Ú F(1, 1, …, 1, 0) Ù x1 Ù x2 Ù … Ù xn-1 Ù Ø xn Ú (1)

Ú F(1, 1, …, 0, 1) Ù x1 Ù x2 Ù … Ù Ø xn-1 Ù xn Ú

Ú F(0, 0, …, 0) Ù Ø x1 Ù Ø x2 Ù … Ù Ø xn

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

Ясно, что формула (1) полностью определяет функ­цию F. Иначе говоря, значения функции F и формулы (1) совпадают на всех наборах значений пере­менных xi. Например, если x1 принимает значение 0, а осталь­ные переменные принимают значение 1, то функция F принимает значение F(0, 1, 1, …, 1). При этом логическое слагаемое F(0, 1, …, 1) Ù Ø x1 Ù x2 Ù … Ù xn = F(0, 1, …, 1) Ù Ø 0 Ù 1 Ù … Ù 1, входящее в форму­лу (1), принимает также значение F(0, l,..., l), а все ос­тальные логические слагаемые формулы (1) имеют зна­чение 0. Действительно, в них знаки отрицания перед переменными распределяются иначе, чем в рассмотрен­ном слагаемом. Таким образом, при подстановке вместо переменных тех же значений в конъюнкцию войдет символ 0 без знака от­рицания, а символ 1 под знаком отрицания. В таком слу­чае один из членов конъюнкции будет иметь значение 0, и по­этому вся конъюнкция также будет иметь значение 0. В связи с этим на основании закона x Ú 0 = x значением фор­мулы (1) является F(0, l,..., l).



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

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

  • каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F(x1, x2, …, xn),
  • все логические слагаемые формулы различны,
  • ни одно логическое слагаемое формулы не содер­жит одновременно переменную и ее отрицание,
  • ни одно логическое слагаемое формулы не содер­жит одну и ту же переменную дважды,

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

Если функция F(x1, x2, …, xn) задана таблицей ис­тинности, то соответствующая ей формула алгебры ло­гики может быть получена просто. Действительно, для каждого набора значений переменных, на котором фун­кция F(x1, x2, …, xn) принимает значение 1, записывается конъюнкция элементарных переменных высказываний, взяв за член конъюнкции хk, если значение xk на ука­занном наборе значений переменных фун­кции F есть 1 и Ø х, если значение xk есть 0. Дизъюнкция всех записан­ных конъюнкций и будет искомой формулой.

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

x1 X2 x3 F(x1, x2, x3)
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0

Для наборов значений переменных (1, 1, 0), (1,0,1), (0,1,0), (0, 0, 0), на которых функция принимает значение 1, запишем конъюнкции x1 Ù x2 Ù Ø x3, x1 Ù Ø x2 Ù x3, Ø x1 Ù x2 Ù Ø x3, Ø x1 Ù Ø x2 Ù Ø x3. а искомая формула, обладающая свойствами совершенства, будет иметь вид:

x1 Ù x2 Ù Ø x3 Ú x1 Ù Ø x2 Ù x3 Ú Ø x1 Ù x2 Ù Ø x3 Ú Ø x1 Ù Ø x2 Ù Ø x3.

 






Date: 2015-04-23; view: 546; Нарушение авторских прав

mydocx.ru - 2015-2020 year. (0.007 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию