Как составить логическую формулу по задаче - Сайт, где вы сможете решить свои вопросы


0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Выбираем строки, где
и
выписываем конъюнкции всех переменных,
при чем, если переменная в этом наборе
равна 1, то записываем ее саму, а если
переменная = 0, то ее отрицание.

Для данного примера

коньюнкция этих дизъюнкций и будет
искомой формулой:

Определение:Конъюнкция
называетсяэлементарной, если
все переменные, входящие в нее, различны.
Количество букв, входящих в элементарную
конъюнкцию или элементарную дизъюнкцию,
называетсярангом.

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

Строго доказано, что любую формулу
булевой алгебры можно выразить с помощью
операций , &,.
Интуитивно этот факт очевиден, вспомним
алгоритм составления формулы по таблице
истинности. При этом мы используем
только эти операции. Такая форма записи
называетсядизъюнктивной нормальной
формой(ДНФ). Это своеобразный механизм
нормализации формул алгебры логики.

Определение:ДНФ– это
дизъюнкция различных элементарных
конъюнкций (т.е. каждая конъюнкция
состоит из элементарных высказываний
или их отрицаний).

Аналогично определяется КНФ – коньюктивная
нормальная форма.

Определение:Если в ДНФ все
элементарные конъюнкции имеют один и
тот же ранг, равный числу переменных,
от которых зависит ДНФ, то она называетсясовершенной (СДНФ).

Теорема. Для любой функции, не
являющейся тождественно ложной,
существует и притом единственная СДНФ.

Следствие. Любую булеву функцию,
не являющуюся тождественно ложной можно
представить в виде суперпозиции&,,,
причем отрицание относится только к
переменным.

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

Системы {&,,};
{,};
{&,},{/}
– являются функционально полными

{&,}
– функционально неполная.

Мы примем эти факты без доказательства,
и решая задачи, будем стараться любую
формулу представить с помощью {&,,}.
Позже мы более подробно обсудим вопрос
функциональной полноты и неполноты
системы операций.

Тема 1.7. Методы упрощения логических выражений. Методы решения логических задач.

Рассмотрим пример решения логической
задачи.

Пример:

После обсуждения состава участников
экспедиции решено, что должны выполняться
два условия.

Если поедет Арбузов, то должны ехать
Брюквин или Вишневский
Если поедут Арбузов и Вишневский то
поедет Брюквин

Составить логическую формулу принятия
решения в символической форме, упростить
полученную формулу и сформулировать
по ней новое условие формирования
экспедиции.

Введём переменные и соответствующие
им элементарные высказывания.

– поедет Арбузов

– поедет Брюквин

– поедет Вишневский

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

Составим общую формулу и упростим
выражение

т.е. если поедет Арбузов, то поедет
Брюквин.

Пример:

Если завтра будет хорошая погода, то мы
пойдем на пляж или поедем в лес. Составим
формулу нашего поведения на завтра.

–
хорошая погода

– мы пойдем на пляж

– мы поедем в лес

Теперь построим отрицание этой фразы

т.о. получим высказывание “Завтра
будет хорошая погода, и мы не пойдем в
лес и на пляж.

Желающие могут построить таблицу
истинности и проверить это утверждение.

Пример:

По подозрению в совершенном преступлении,
задержаны Браун, Джон и Смит. Один из
них уважаемый в городе старик, второй
чиновник, а третий известный мошенник.
В ходе следствия старик говорил правду,
мошенник лгал, а третий задержанный в
одном случае говорил правду, а в другом
лгал.

Вот что они говорили:

Браун: Я совершил это. Джон не виноват.
(Б&Д)

Джон: Браун не виноват. Преступник Смит.
(Б&С)

Смит: Я не виноват. Виноват Браун (С&Б)

Опишем эти высказывания формально:

– преступление совершил Браун

– преступление совершил Джон

– преступление совершил Смит

Тогда их слова описываются следующими
выражениями:

Браун:

Джон:

Смит:

Т.к. по условиям задачи две из этих &ложны и одна истинна, то

Составим таблицу истинности

NN
1	0	0	0	0	0	0	0
2	0	0	1	0	1	0	1
3	0	1	0	0	0	0	0
4	0	1	1	0	1	0	1
5	1	0	0	1	0	1	1
6	1	0	1	1	0	0	1
7	1	1	0	0	0	1	1
8	1	1	1	0	0	0	0

Исключим из рассмотрения те наборы, на
которых
(по условию задачи одна из&- истинна, следовательно,)
1, 3, 8
Исключим случай 5, т.к. в нем две &истинны, что противоречит условию
задачи.
В случаях 4, 6, 7 у нас в начальном наборе
две 1 , т.е. 2 преступника, а по условию
задачи он один.

Остается только случай 2 , т.е. преступник
Смит, и оба его высказывания ложны.

следовательно–
ложно и–
истинно

=
1 – Джон уважаемый старик

Остается, что Браун чиновник, и поскольку
– ложно , то– истинно.

Пользуясь законами и тождествами булевой
алгебры можно упрощать логические
выражения.

Пример:

Упражнение:

(X&Y&Z)(X&Y&Z)X&Y

Соседние файлы в папке Коспект лекций

#
16.03.2016266 б10desktop.ini
#
16.03.201611.67 Кб10Folder.htt
#
#
#
#
#
#

Источник

Для любой логической формулы можно построить бесконечное количество равносильных ей формул. Для этого потребуется произвести некоторое количество тождественных преобразований. Одной из главных задач в алгебре логики является нахождение канонических форм формул. Проще говоря таких, которые построены по одному канону (правилу).

Форма представления какой-либо логической функции будет считаться нормальной, если она выражена через конъюнкцию, дизъюнкцию, а также отрицание переменных. Среди всех нормальных форм можно выделить совершенно нормальные. Это тот случай, когда функция может быть записана только одним единственным способом.

Классы СКНФ и СДНФ

В при решении задач в алгебре логики особая роль отводится классам конъюнктивных и дизъюнктивных совершенно нормальных форм. Они основаны на стандартных понятиях элементарной конъюнкции и дизъюнкции.

Определение 1 — 2

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

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

СКНФ

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

КНФ – конъюнктивная нормальная форма, представляющая собой конъюнкцию нескольких дизъюнкций. К примеру, [(A vee bar{B} vee C) wedge(A vee C)];
ДНФ – дизъюнктивная нормальная форма, которая является дизъюнкцией нескольких конъюнкций. К примеру, [(A wedge bar{B} wedge C) vee(A wedge C)].

Определение 3

Совершенной конъюнктивной нормальной формой (СКНФ) называют КНФ, удовлетворяющую нескольким условиям:

В ней не содержится двух и более элементарных дизъюнкций;
Во всех дизъюнкциях отсутствуют одинаковые переменные;
Каждая ДНФ содержит в себе все переменные из входящих в нее КНФ.

Любую булеву формулу, не являющуюся тождественной истиной, можно представить в виде СКНФ.

Правила построения СКНФ

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

Построение должно осуществляться по следующему алгоритму:

В таблице нужно отметить такие наборы переменных, при которых [f=1].
Для каждого выбранного набора переменных записываем КНФ, при этом если значение какой-либо из них равно 1, то она включается в неизменном виде, иначе – ее отрицание.
На последнем этапе все полученные конъюнкции следует связать операциями дизъюнкции.

СНДФ

Определение 4

Совершенной дизъюнктивной нормальной формой (СНДФ) называют удовлетворяющую нескольким условиям ДНФ. Всего должно выполняться три условия:

В ДНФ не должно содержаться двух и более одинаковых СКНФ.
Ни в одной из конъюнкций не должно содержаться одинаковых переменных.
В каждой элементарной КНФ должны содержаться все переменные, входящих в нее ДНФ, при этом их порядок должен полностью совпадать.

Любую булеву формулу в алгебре логики, не являющуюся тождественно ложной, можно представить в виде СНДФ, но только в одном единственном виде.

Правила построения СДНФ

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

Алгоритм построения будет следующим:

В таблице отмечаются все те наборы переменных, при которых [f=0]
Для каждого отмеченного набора всех переменных записывается ДНФ, при этом если значение какой-либо из них равно нулю, то включается сама переменная, в любом другом случае ее нужно инвертировать.
В конце все полученные дизъюнкции связываются друг с другом операциями конъюнкции.

Нет времени решать самому?

Наши эксперты помогут!

Примеры нахождения СКНФ и СДНФ

Рассмотрим несколько примеров нахождения СКНФ и СДНФ с помощью данных таблицы истинности.

Примеры 1 — 2

Необходимо по таблице истинности записать логическую функцию.

Решение. Для того чтобы выполнить задачу будем использовать правило построения СДНФ.

Получим СДНФ, которая имеет следующий вид:

[Fleft(x_{1}, x_{2}, x_{3}right)=left(overline{x_{1}} wedge overline{x_{2}} wedge overline{x_{3}}right) veeleft(overline{x_{1}} wedge overline{x_{2}} wedge x_{3}right) veeleft(x_{1} wedge overline{x_{2}} wedge overline{x_{3}}right) veeleft(x_{1} wedgeright.left.overline{x_{2}} wedge x_{3}right) veeleft(x_{1} wedge x_{2} wedge x_{3}right)]
Далее будем действовать согласно правилу построения СКНФ:

В результате получим:

[Fleft(x_{1}, x_{2}, x_{3}right)=left(x_{1} wedge overline{x_{2}} wedge x_{3}right) wedgeleft(x_{1} wedge overline{x_{2}} wedge overline{x_{3}}right) wedgeleft(overline{x_{1}} wedge overline{x_{2}} wedge x_{3}right)]

Требуется представить функцию, которая задана в таблице в виде СДНФ и СКНФ.

Решение: Для начала запишем в СНДФ заданную логическую функцию. Чтобы было проще, добавим еще один вспомогательный столбец. Руководствуемся правилом составления СДНФ и учитываем, что требуется ввести знак отрицания, если значение переменной будет нулевым. Это нужно для того, чтобы они не превратили в нули основной функции значение конъюнкции.

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

[Fleft(x_{1}, x_{2}, x_{3}, x_{4}right)=(bar{x} wedge bar{y} wedge z wedge f) veeleft(overline{x_{1}} wedge overline{x_{2}} wedge overline{x_{3}} wedge overline{x_{4}}right) veeleft(overline{x_{1}} wedge x_{2} wedge x_{3} wedgeright.left.x_{4}right) veeleft(x_{1} wedge overline{x_{2}} wedge overline{x_{3}} wedge overline{x_{4}}right)]

После этого потребуется записать логическую функцию в СКНФ. Для этого используем правило ее составления и вводим знаки отрицания для тех переменных, значение которых равно 1. Если пренебречь инвертированием единичных значений, то они могут превратить ДНФ в единицы основных функций.

Все полученные нами значения во вспомогательном столбце соединяем знаком конъюнкции и в итоге получаем логическую функцию в следующем виде.
[Fleft(x_{1}, x_{2}, x_{3}, x_{4}right)=left(x_{1} vee x_{2} vee x_{3} vee x_{4}right) wedgeleft(x_{1} vee x_{2} vee x_{3} vee overline{x_{4}}right) wedgeleft(x_{1} vee x_{2} veeright.\left.overline{x_{3}} vee x_{4}right) wedgeleft(x_{1} vee overline{x_{2}} vee x_{3} vee overline{x_{4}}right) wedgeleft(x_{1} vee overline{x_{2}} vee overline{x_{3}} vee x_{4}right) wedgeleft(overline{x_{1}} vee x_{2} vee x_{3} veeright.\left.overline{x_{4}}right) wedgeleft(overline{x_{1}} vee x_{2} vee overline{x_{3}} vee x_{4}right) wedgeleft(overline{x_{1}} vee x_{2} vee overline{x_{3}} vee overline{x_{4}}right) wedgeleft(overline{x_{1}} vee overline{x_{2}} vee x_{3} vee x_{4}right) wedge\left(overline{x_{1}} vee overline{x_{2}} vee x_{3} vee overline{x_{4}}right) wedgeleft(overline{x_{1}} vee overline{x_{2}} vee overline{x_{3}} vee x_{4}right) wedgeleft(overline{x_{1}} wedge overline{x_{2}} wedge overline{x_{3}} wedge overline{x_{4}}right)]
После рассмотрения примеров построения СДНФ и СКНФ с использованием таблицы истинности, стал понятен принцип построения логических функций.

Источник

Решение логических задач

Разнообразие логических задач очень велико. Способов их решения тоже немало. Но наибольшее распространение получили следующие три способа решения логических задач:

средствами алгебры логики;
табличный;
с помощью рассуждений.

Познакомимся с ними поочередно.

Решение логических задач средствами алгебры логики

Обычно используется следующая схема решения:

1. изучается условие задачи;

2. вводится система обозначений для логических высказываний;

3. конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;

4. определяются значения истинности этой логической формулы;

5. из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.

Пример 1. Трое друзей, болельщиков автогонок «Формула-1», спорили о результатах предстоящего этапа гонок.

— Вот увидишь, Шумахер не придет первым, — сказал Джон. Первым будет Хилл.

— Да нет же, победителем будет, как всегда, Шумахер, — воскликнул Ник. — А об Алези и говорить нечего, ему не быть первым.

Питер, к которому обратился Ник, возмутился:

— Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.

По завершении этапа гонок оказалось, что каждое из двух предположений двоих друзей подтвердилось, а оба предположения третьего из друзей оказались неверны. Кто выиграл этап гонки?

Решение. Введем обозначения для логических высказываний:

Ш — победит Шумахер; Х — победит Хилл; А — победит Алези.

Реплика Ника «Алези пилотирует самую мощную машину» не содержит никакого утверждения о месте, которое займёт этот гонщик, поэтому в дальнейших рассуждениях не учитывается.

Зафиксируем высказывания каждого из друзей:

Джон: ¬Ш/Х

Ник: Ш/¬А

Питер: ¬Х

Высказывание Ш / ¬ А/ ¬Х истинно только при Ш=1, А=0, Х=0.

Ответ. Победителем этапа гонок стал Шумахер.

Решение логических задач табличным способом

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

Пример 2. В симфонический оркестр приняли на работу трёх музыкантов: Брауна, Смита и Вессона, умеющих играть на скрипке, флейте, альте, кларнете, гобое и трубе.

Известно, что:

Смит самый высокий;
играющий на скрипке меньше ростом играющего на флейте;
играющие на скрипке и флейте и Браун любят пиццу;
когда между альтистом и трубачом возникает ссора, Смит мирит их;
Браун не умеет играть ни на трубе, ни на гобое.

На каких инструментах играет каждый из музыкантов, если каждый владеет двумя инструментами?

Решение. Составим таблицу и отразим в ней условия задачи, заполнив соответствующие клетки цифрами 0 и 1 в зависимости от того, ложно или истинно соответствующее высказывание.

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

Из условия 4 следует, что Смит не играет ни на альте, ни на трубе, а из условий 3 и 5, что Браун не умеет играть на скрипке, флейте, трубе и гобое. Следовательно, инструменты Брауна — альт и кларнет. Занесем это в таблицу, а оставшиеся клетки столбцов «альт» и «кларнет» заполним нулями:

Из таблицы видно, что на трубе может играть только Вессон.

Из условий 1 и 2 следует, что Смит не скрипач. Так как на скрипке не играет ни Браун, ни Смит, то скрипачом является Вессон. Оба инструмента, на которых играет Вессон, теперь определены, поэтому остальные клетки строки «Вессон» можно заполнить нулями:

Из таблицы видно, что играть на флейте и на гобое может только Смит.

Ответ: Браун играет на альте и кларнете, Смит — на флейте и гобое, Вессон — на скрипке и трубе.

Решение логических задач с помощью рассуждений

Этим способом обычно решают несложные логические задачи.

Пример 3. Вадим, Сергей и Михаил изучают различные иностранные языки: китайский, японский и арабский. На вопрос, какой язык изучает каждый из них, один ответил: «Вадим изучает китайский, Сергей не изучает китайский, а Михаил не изучает арабский». Впоследствии выяснилось, что в этом ответе только одно утверждение верно, а два других ложны. Какой язык изучает каждый из молодых людей?

Решение. Имеется три утверждения:

Вадим изучает китайский;
Сергей не изучает китайский;
Михаил не изучает арабский.

Если верно первое утверждение, то верно и второе, так как юноши изучают разные языки. Это противоречит условию задачи, поэтому первое утверждение ложно.

Если верно второе утверждение, то первое и третье должны быть ложны. При этом получается, что никто не изучает китайский. Это противоречит условию, поэтому второе утверждение тоже ложно.

Остается считать верным третье утверждение, а первое и второе — ложными. Следовательно, Вадим не изучает китайский, китайский изучает Сергей.

Ответ: Сергей изучает китайский язык, Михаил — японский, Вадим — арабский.

Пример 4. Министры иностранных дел России, США и Китая обсудили за закрытыми дверями проекты соглашения о полном разоружении, представленные каждой из стран. Отвечая затем на вопрос журналистов: «Чей именно проект был принят?», министры дали такие ответы:

Россия — «Проект не наш, проект не США»;
США — «Проект не России, проект Китая»;
Китай — «Проект не наш, проект России».

Один из них (самый откровенный) оба раза говорил правду; второй (самый скрытный) оба раза говорил неправду, третий (осторожный) один раз сказал правду, а другой раз — неправду.

Определите, представителями каких стран являются откровенный, скрытный и осторожный министры.

Решение. Для удобства записи пронумеруем высказывания дипломатов:

Россия — «Проект не наш» (1), «Проект не США» (2);
США — «Проект не России» (3), «Проект Китая» (4);
Китай — «Проект не наш» (5), «Проект России» (6).

Узнаем, кто из министров самый откровенный.

Если это российский министр, то из справедливости (1) и (2) следует, что победил китайский проект. Но тогда оба утверждения министра США тоже справедливы, чего не может быть по условию.

Если самый откровенный — министр США, то тогда вновь получаем, что победил китайский проект, значит оба утверждения российского министра тоже верны, чего не может быть по условию.

Получается, что наиболее откровенным был китайский министр. Действительно, из того, что (5) и (6) справедливы, cледует, что победил российский проект. А тогда получается, что из двух утверждений российского министра первое ложно, а второе верно. Оба же утверждения министра США неверны.

Ответ: Откровеннее был китайский министр, осторожнее — российский, скрытнее — министр США.

Источник

Решение задач

Пример

Составить логическую схему для следующего логического выражения найдите ответ:

F = X V Y & X

( пусть Х – истина, Y – ложь)

Строим схему:

Ответ: 1 V 0 & 1 =

Пример

Постройте логическую схему, соответствующую логическому выражению F = X & Y V ¬(Y V X) . Вычислить значения выражения для X=1 , Y=0 .

Постройте логическую схему по логическому выражению и найдите значение логического выражения

F = A V B& ¬ C , если А=1, В=1, С=1

F = ¬ ( A V B&C ), если А=0, В=1, С=1

F = ¬ A V B&C , если А=1, В=0, С=1

F = ( A V B ) & ( C V B ), если А=0, В=1, С= 0

Постройте логическую схему по логическому выражению и найдите значение логического выражения

F = ¬ ( A&B&C ) V (B&C V ¬A ) , если А= 1 , В=1, С= 0

F = ¬ ( A&B&C ), если А=0, В= 0 , С=1

F = B& ¬ A V ¬B &A , если А=0, В= 0

Постройте логическое выражение по логической схеме

Ответ : F = A & (B V C)

Постройте логическое выражение по логической схеме

Ответ : F = (A V( ¬A & B)) & ¬B

Постройте логическое выражение по логической схеме

Ответ : F = A&B&( ¬ B V ¬ C) V D

Постройте логическое выражение по логической схеме

Ответ : F = (¬A& C ) V ¬ (A&BVB&C)

Домашнее задание

Составьте логические схемы к логическим выражениям:

F = BV(C& ¬A)V(A&B)

F = ¬(A&B)VC&D

Источник

Информатика, 10 класс. Урок № 12.

Тема — Преобразование логических выражений

Перечень вопросов, рассматриваемых в теме: основные законы алгебры логики, преобразование логических выражений, логические функции, построение логического выражения с данной таблицей истинности и его упрощение, дизъюнктивная и конъюнктивная нормальная форма, совершенная дизъюнктивная нормальная форма (СДНФ), совершенная конъюнктивная нормальная форма (СКНФ).

Глоссарий по теме: основные законы алгебры логики, логические функции, дизъюнктивная и конъюнктивная нормальная форма, совершенная дизъюнктивная нормальная форма (СДНФ), совершенная конъюнктивная нормальная форма (СКНФ)

Основная литература по теме урока:

Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 10 класса

— М.: БИНОМ. Лаборатория знаний, 2017 (с.197—209)

Открытые электронные ресурсы по теме:

http://lbz.ru/metodist/authors/informatika/3/eor10.php

http://kpolyakov.spb.ru/school/ege.htm

Теоретический материал для самостоятельного изучения.

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

Основные законы алгебры логики

Справедливость законов можно доказать построением таблиц истинности.

Пример 1. Упростим логическое выражение

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

В общем случае можно предложить следующую последовательность действий:

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

Пример 2. Упростим логическое выражение .

Здесь последовательно использованы замена операции импликация, закон де Моргана, распределительный закон, закон противоречия и операция с константой, закон идемпотентности и поглощения.

Аналогичные законы выполняются для операции объединения, пересечения и дополнения множеств. Например:

Пример 3. На числовой прямой даны отрезки B = [2;12] и C = [7;18]. Каким должен быть отрезок A, чтобы предикат становился истинным высказыванием при любых значениях x.

Преобразуем исходное выражение, избавившись от импликации:

A, B, C — множества. Для них можно записать (U — универсальное множество).

Будем считать, что.

Тогда , причем это минимально возможное множество А.

Так как множество B — это отрезок [2;12], а множество — это промежутки и, то пересечением этих множеств будет служить промежуток . В качестве ответа мы можем взять этот промежуток, а также любой другой, его включающий.

Пример 4. Для какого наименьшего неотрицательного целого десятичного числа а выражение

тождественно истинно (т. е. принимает значение 1 при любом неотрицательном целом значении десятичной переменной х)? Здесь & — поразрядная конъюнкция двух неотрицательных целых десятичных чисел.

Введем обозначения:

Перепишем исходное выражение в наших обозначениях и преобразуем его:

Рассмотрим предикат . В числе 28₁₀=11100₂ 4-й, 3-й и 2-й биты содержат единицы, а 1-й и 0-й — нули. Следовательно, множеством истинности этого предиката являются такие числа х, у которых хотя бы один из битов с номерами 4, 3 или 2 содержит единицу. Если и 4-й, и 3-й, и 2-й биты числа х нулевые, то высказывание будет ложным.

Рассмотрим предикат . В числе 45₁₀=101101₂ 5-й, 3-й, 2-й и 0-й биты содержат единицы, 4-й и 1-й — нули. Следовательно, множеством истинности этого предиката являются такие числа х, у которых хотя бы один из битов с номерами 5, 3, 2 или 0 содержит единицу. Если и 5-й, и 3-й, и 2-й, и 0-й биты числа х нулевые, то высказывание будет ложным.

Рассмотрим предикат . В числе 17₁₀=10001₂ 3-й, 2-й и 1-й биты содержат нули, 4-й и 0-й — единицы. Побитовая конъюнкция 17 и х будет равна 0, если в числе х 4-й и 0-й биты будут содержать нули. Множество истинности этого предиката — все х с нулями в 4-м и 0-м битах.

По условию задачи надо, чтобы .

Запишем это выражение для рассмотренных множеств истинности:

Так как , примем .

Объединением множеств M и N являются все двоичные числа, у которых хотя бы один из битов с номерами 5, 4, 3, 2, 0 содержит единицу. Пересечением этого множества с множеством K будут все двоичные числа, у которых биты с номерами 4 и 0 будут заняты нулями, т.е. такие двоичные числа, у которых хотя бы один из битов с номерами 5, 3, 2 содержит 1. Все эти числа образуют множество А.

Искомое число a должно быть таким, чтобы при любом неотрицательном целом значении переменной х: , и, кроме того, оно должно быть минимальным из возможных. Этим условиям удовлетворяет число 101100₂= 44₁₀.

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

Совокупность значений n аргументов удобно интерпретировать как строку нулей и единиц длины n. Существует ровно различных двоичных строк длины n. Так как на каждой такой строке некая функция может принимать значение 0 или 1, общее количество различных булевых функций от n аргументов равно .

Для n=2 существует 16 различных логических функций. Рассмотрим их подробнее.

A	B	F₁	F₂	F₃	F₄	F₅	F₆	F₇	F₈	F₉	F₁₀	F₁₁	F₁₂	F₁₃	F₁₄	F₁₅	F₁₆
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

F₁(A,B) = 0 — константа «ложь»;

F₂(A,B) = A&B — конъюнкция;

F₃(A,B) = — отрицание импликации;

F₄(A,B) = A — функция, равная первому аргументу;

F₅(A,B) = — отрицание обратной импликации;

F₆(A,B) = B — функция, равная второму аргументу;

F₇(A,B) = — строгая дизъюнкция;

F₈(A,B) = A˅B — дизъюнкция;

F₉(A,B) = — стрелка Пирса (отрицание дизъюнкции, ИЛИ-НЕ);

F₁₀(A,B) = — эквиваленция;

F₁₁(A,B) = — отрицание второго аргумента;

F₁₂(A,B) = — обратная импликация;

F₁₃(A,B) = — отрицание первого аргумента;

F₁₄(A,B) = — импликация;

F₁₅(A,B) = — штрих Шеффера (отрицание конъюнкции, И-НЕ);

F₁₆(A,B) = 1 — константа «истина».

С увеличением числа аргументов количество логических функций резко возрастает. Отметим, что путем преобразований функция любого количества переменных может быть выражена через функции только двух переменных. Более того, можно использовать не все, а лишь некоторые логические функции двух переменных. Например:

F₂ и F₁₁ (конъюнкция и отрицание второго аргумента);
F₈ и F₁₃ (дизъюнкция и отрицание первого аргумента);
F₉(стрелка Пирса, отрицание дизъюнкции);
F₁₅(штрих Шеффера, отрицание конъюнкции).

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

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

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

При решении задач часто требуется по таблице истинности логической формулы записать ее аналитическое выражение. Для этого используются понятия совершенной дизъюнктивной нормальной формы (СДНФ) и совершенной конъюнктивной нормальной формы (СКНФ).

Простой конъюнкцией называется конъюнкция одной или нескольких переменных, в которой каждая переменная встречается не более одного раза (либо сама, либо ее отрицание). Например, запись является простой конъюнкцией.

Аналогично, выражение — простая дизъюнкция.

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций. Например, выражение является ДНФ.

Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций. Например, выражение является КНФ.

Совершенной дизъюнктивной нормальной формой (СДНФ) называется такая дизъюнктивная нормальная форма, у которой в каждую конъюнкцию входят все переменные (либо сами, либо их отрицания). Например, выражение является ДНФ, но не СДНФ. Выражение же представляет собой СДНФ.

Совершенной конъюнктивной нормальной формой (СКНФ) называется такая КНФ, у которой в каждую простую дизъюнкцию входят все переменные (либо сами, либо их отрицания). Например, выражение представляет собой СКНФ.

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

Отметить в таблице истинности наборы переменных, при которых значение логического выражения равно единице;
Для каждого отмеченного набора записать конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае — её отрицание;
Все полученные конъюнкции связать операциями дизъюнкции.

Пример 5. Имеется следующая таблица истинности: