Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Представление произвольной логической функции в виде формулы алгебры логики
|
|
Пусть с помощью таблицы истинности задана произвольная функция алгебры логики n переменных F (x 1, x 2, …, x n). Рассмотрим формулу:
F (1, 1, …, 1) Ù x 1 Ù x 2 Ù … Ù x n Ú
Ú F (1, 1, …, 1, 0) Ù x 1 Ù x 2 Ù … Ù x n-1 Ù Ø x n Ú (1)
Ú F (1, 1, …, 0, 1) Ù x 1 Ù x 2 Ù … Ù Ø x n-1 Ù x n Ú
Ú F (0, 0, …, 0) Ù Ø x 1 Ù Ø x 2 Ù … Ù Ø x n
которая составлена следующим образом: каждое слагаемое этой логической суммы представляет собой конъюнкцию, в которой первый член является значением функции F при некоторых определенных значениях ее переменных, остальные же члены конъюнкции представляют собой сами переменные или их отрицания. При этом под знаком отрицания находятся те и только те переменные, которые в первом члене конъюнкции имеют значение 0.
Ясно, что формула (1) полностью определяет функцию F. Иначе говоря, значения функции F и формулы (1) совпадают на всех наборах значений переменных xi. Например, если x 1 принимает значение 0, а остальные переменные принимают значение 1, то функция F принимает значение F (0, 1, 1, …, 1). При этом логическое слагаемое F (0, 1, …, 1) Ù Ø x 1 Ù x 2 Ù … Ù x n = 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 (x 1, x 2, …, x n),
- все логические слагаемые формулы различны,
- ни одно логическое слагаемое формулы не содержит одновременно переменную и ее отрицание,
- ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды,
Перечисленные свойства будем называть свойствами совершенства или, коротко, свойствами. Из приведенных рассуждений видно, что каждой не тождественно ложной функции соответствует единственная формула указанного вида.
Если функция F (x 1, x 2, …, x n) задана таблицей истинности, то соответствующая ей формула алгебры логики может быть получена просто. Действительно, для каждого набора значений переменных, на котором функция F (x 1, x 2, …, x n) принимает значение 1, записывается конъюнкция элементарных переменных высказываний, взяв за член конъюнкции хk, если значение xk на указанном наборе значений переменных функции F есть 1 и Ø х, если значение xk есть 0. Дизъюнкция всех записанных конъюнкций и будет искомой формулой.
Пусть, например, функция F (x 1, x 2, x 3) имеет следующую таблицу истинности:
| x 1 | X 2 | x 3 | F (x 1, x 2, x 3) |
| 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, запишем конъюнкции x 1 Ù x 2 Ù Ø x 3, x 1 Ù Ø x 2 Ù x 3, Ø x 1 Ù x 2 Ù Ø x 3, Ø x 1 Ù Ø x 2 Ù Ø x 3. а искомая формула, обладающая свойствами совершенства, будет иметь вид:
x 1 Ù x 2 Ù Ø x 3 Ú x 1 Ù Ø x 2 Ù x 3 Ú Ø x 1 Ù x 2 Ù Ø x 3 Ú Ø x 1 Ù Ø x 2 Ù Ø x 3.
Date: 2015-04-23; view: 844; Нарушение авторских прав