Ассоциативность

х 1 (х 2 х 3) = (х 1 х 2)х 3 ;

х 1 Ú (х 2 Ú х 3) = (х 1 Ú х 2) Ú х 3 .

Коммутативность

х 1 х 2 = х 2 х 1

х 1 Ú х 2 = х 2 Ú х 1

Дистрибутивность конъюнкции относительно дизъюнкции

х 1 (х 2 Ú х 3) = х 1 х 2 Ú х 1 х 3 .

Дистрибутивность дизъюнкции относительно конъюнкции

х 1 Ú(х 2 × х 3) = (х 1 Úх 2) × (х 1 Úх 3). *

Идемпотентность (тавтология)

Двойное отрицание

Свойства констант

x & 1 = x; (законы универсального множества)

x & 0 = 0; (законы нулевого множества)

Правила (законы) де Моргана

Закон противоречия (дополнительности)

Закон исключения третьего (дополнительности)

Доказательства всех этих формул тривиальны. Один из вариантов –построение таблиц истинности левой и правой частей и их сравнение.

Правила склеивания

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

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

Правило поглощения

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

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

Правило развертывания

Это правило определяет действие обратное склеиванию.

Правило развертывания элементарного произведения в логическую сумму элементарных произведений большего ранга (в пределе до r = n, т.е. до конституент единицы, как и будет рассмотрено ниже) следует из законов универсального множества, распределительного закона первого рода и производится в три этапа:

В развертываемое элементарное произведение ранга r вводится в качестве сомножителей n-r единиц, где n- ранг конституенты единицы;

Каждая единица заменяется логической суммой некоторой, не имеющейся в исходном элементарном произведении переменной и ее отрицания: x i v `x i = 1;

Производится раскрытие всех скобок на основе распределительного закона первого рода, что приводит к развертыванию исходного элементарного произведения ранга r в логическую сумму 2 n-r конституент единицы.

Правило развертывания элементарного произведения используется для минимизации функций алгебры логики (ФАЛ).

Правило развертывания элементарной суммы ранга r до произведения элементарных сумм ранга n (конституент нуля) следует их законов нулевого множества (6) и распределительного закона второго рода (14) и производится в три этапа:

В развертываемую сумму ранга r в качестве слагаемых вводится n-r нулей;

Каждый нуль представляется в виде логического произведения некоторой, не имеющейся в исходной сумме переменной и ее отрицания: x i ·`x i = 0;

Получившееся выражение преобразуется на основе распределительного закона второго рода (14) таким образом, чтобы исходная сумма ранга r развернулась в логическое произведение 2 n-r конституент нуля.

16.Понятие полной системы. Примеры полных систем (с доказательством)

Определение. Множество функций алгебры логики A называется полной системой (в P2), если любую функцию алгебры логики можно выразить формулой над A.

Система функций A={ f 1 , f 1 ,…, f m }, являющаяся полной, называется базисом .

Минимальным базисом называется такой базис, для которого удаление хотя бы одной функции f 1 , образующей этот базис, превращает систему функций (f 1 , f 1 ,…, f m) в неполную.

Теорема. Система A = {∨, &, } является полной.

Доказательство. Если функция алгебры логики f отлична от тождественного нуля, то f выражается в виде совершенной дизъюнктивной нормальной формы, в которую входят лишь дизъюнкция, конъюнкция и отрицание. Если же f ≡ 0, то f = x & x . Теорема доказана.

Лемма. Если система A - полная, и любая функция системы A может быть выражена формулой над некоторой другой системой B, то B - также полная система.

Доказательство. Рассмотрим произвольную функцию алгебры логики f (x 1 , …, x n) и две системы функций: A = {g 1 , g 2 , …} и B = {h 1 , h 2 , …}. В силу того, что система A полна, функция f может быть выражена в виде формулы над ней:

f (x 1 , …, x n) = ℑ

где g i = ℜ i

то есть функция f представляется в виде

f (x 1 , …, x n)=ℑ[ℜ1,ℜ2,...]

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

Теорема. Следующие системы являются полными в P 2:

4) {&, ⊕ , 1}базис Жегалкина.

Доказательство.

1) Известно (теорема 3), что система A = {&, V, } полна. Покажем, что полна система B = { V, . Действительно, из закона де Моргана (x& y) = (x ∨ y) получаем, что x & y = (x ∨ y) , то есть конъюнкция выражается через дизъюнкцию и отрицание, и все функции системы A выражаются формулами над системой B. Согласно лемме система B полна.

2) Аналогично пункту 1: (x ∨ y) = x & y ⇔ x ∨ y =(x & y) и из леммы 2 следует истинность утверждения пункта 2.

3) x | y=(x&y), x | x = x ; x & y = (x | y) = (x | y) | (x | y) и согласно лемме 2 система полна.

4) x = x ⊕1 и согласно лемме 2 система полна.

Теорема доказана.

17.Алгебра Жегалкина. Свойства операций и полнота

Множество булевых функций, заданных в базисе Жегалкина S4={⊕,&,1} называется алгеброй Жегалкина .

Основные свойства.

1. коммутативность

h1⊕h2=h2⊕h1 h1&h2=h2&h1

2. ассоциативность

h1⊕(h2⊕h3)=(h1⊕h2)⊕h3 h1&(h2&h3)=(h1&h2)&h3

3. дистрибутивность

h1&(h2⊕h3)=(h1&h2)⊕(h1&h3)

4. свойства констант

5. h⊕h=0 h&h=h
Утверждение . Через операции алгебры Жегалкина можно выразить все другие булевы функции:

x→y=1⊕x⊕xy

x↓y=1⊕x⊕y⊕xy

18.Полином Жегалкина. Способы построения. Пример.

Полиномом Жегалкина (полиномом по модулю 2) от n переменных x 1 ,x 2 ... x n называется выражение вида:

c 0 ⊕c 1 x 1 ⊕c 2 x 2 ⊕ ... ⊕c n x n ⊕c 12 x 1 x 2 ⊕ ... ⊕c 12 ... n x 1 x 2 ... x n ,

где постоянные C k могут принимать значения 0 ли 1.

Если полином Жегалкина не содержит произведений отдельных переменных, то он называется линейным (линейная функция).

Например, f=x⊕yz⊕xyz и f 1 =1⊕x⊕y⊕z - полиномы, причем вторая является линейной функцией.

Теорема . Каждая булева функция представляется в виде полинома Жегалкина единственным образом.

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

1. Метод неопределенных коэффициентов. Пусть P(x 1 ,x 2 ... x n) - искомый полином Жегалкина, реализующий заданную функцию f(x 1 ,x 2 ... x n). Запишем его в виде

P=c 0 ⊕c 1 x 1 ⊕c 2 x 2 ⊕ ... ⊕c n x n ⊕c 12 x 1 x 2 ⊕ ... ⊕c 12 ... n x 1 x 2 ... x n

Найдем коэффициенты C k . Для этого последовательно придадим переменным x 1 ,x 2 ... x n значения из каждой строки таблицы истинности. В итоге получим систему из 2 n уравнений с 2 n неизвестными, имеющую единственное решение. Решив ее, находим коэффициенты полинома P(X 1 ,X 2 ... X n).

2. Метод, основанный на преобразовании формул над множеством связок {,&}. Строят некоторую формулу F над множеством связок {,&}, реализующую данную функцию f(X 1 ,X 2 ... X n). Затем заменяют всюду подформулы вида A на A⊕1, раскрывают скобки, пользуясь дистрибутивным законом (см. свойство 3), а затем применяют свойства 4 и 5.

Пример . Построить полином Жегалкина функции f(X,Y)=X→Y

Решение .
1. (метод неопределенных коэффициентов). Запишем искомый полином в виде:

P=c 0 ⊕c 1 x⊕c 2 y⊕c 12 xy

Пользуясь таблицей истинности импликации получаем, что

f(0,0)=P(0,0)=C 0 =1

f(0,1)=P(0,1)=C 0 ⊕C 2 =1

f(1,0)=P(1,0)=C 0 ⊕C 1 =0

f(1,1)=P(1,1)=C 0 ⊕C 1 ⊕C 2 ⊕C 12 =1

Откуда последовательно находим, C 0 =1, C 1 =1, C 2 =0, C 12 =1

Следовательно: x→y=1⊕X⊕XY.

2. (Метод преобразования формул.). Имеем: x→y=xvy=(xy)=(x(y⊕1)) ⊕1=1⊕x⊕xy
Заметим, что преимущество алгебры Жегалкина (по сравнению с другими алгебрами) состоит в арифметизации логики, что позволяет выполнять преобразования булевых функций довольно просто. Ее недостатком по сравнению с булевой алгеброй является громоздкость формул.

Похожая информация.

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

Для произвольных множеств А, В, и С справедливы следующие тождества (табл. 3.1):

Таблица 3.1

Законы алгебры множеств по отношению к операциям пересечения () и объединения () подчинены принципу двойственности: если в каком-либо законе все знаки пересечения заменить знаками объединения, а все знаки объединения – знаками пересечения, знак универсума (U) заменить знаком пустого множества (Ø), а знак пустого – знаком универсума, то получим снова верное тождество. Например (в силу этого принципа), из следует и т. п.

3.1. Проверка истинности тождеств при помощи диаграмм Эйлера-Венна

Все законы алгебры множеств можно наглядно представить и доказать, используя диаграммы Эйлера-Венна. Для этого необходимо:

Начертить соответствующую диаграмму и заштриховать все множества, стоящие в левой части равенства.

Начертить другую диаграмму и сделать то же для правой части равенства.

Данное тождество истинно тогда и только тогда, когда на обеих диаграммах заштрихована одна и та же область.

Замечание 3.1. Два пересекающихся круга делят всё универсальное множество на четыре области (см. рис.3.1)

Замечание 3.2. Три пересекающихся круга делят всё универсальное множество на восемь областей (см. рис.3.2):

Замечание 3.2. При записи условий различных примеров часто используются обозначения:

 - из … следует…;

 - тогда и только тогда, когда… .

Задача 3.1 . Упростить выражения алгебры множеств:

Решение.

Задача 3 .2 . Доказать тождества:

(АВ)\В = А\В;

А(ВС) = А\(А\В)(А\С).

Решение.

Задача 3.3 . Доказать следующие соотношения двумя способами: с помощью диаграмм и с помощью определения равенства множеств.

Решение.

2. Доказательство с помощью определения равенства множеств.

По определению, множества Х и Y равны, если одновременно выполнены соотношения: XY и YX.

Сначала покажем, что
. Пустьх – произвольный элемент множества
, то естьх 
. Это означает, чтох U и х 
. Отсюда вытекает, чтох А или х В. Если х А, то тогда х Ā, а значит,
. Если жех В, то
, а значит,
. Таким образом, всякий элемент множества.
. есть также элементом множества
То есть

Теперь докажем обратное, то есть, что
. Пусть
. Еслих Ā, то х U и х А, а значит, х АВ. Отсюда следует, что
. Если же
, тох U и х В. Значит, х АВ, то есть
. Отсюда следует, что всякий элемент множества
является также элементом множества
, то есть
.

Значит,
, что и требовалось доказать.

A(BC) = (AB)(AC);

1. Доказательство с помощью диаграммы:

Пусть х А(ВС). Тогда х А и х ВС. Если х В, то х АВ, что не противоречит сказанному, а значит, х (АВ)(АС). Если же х С, то х АС. Следовательно, х (AB)(AC). Итак, доказано, что A(BC)  (AB)(AC.

Пусть теперь х  (AB)(AC). Если х АВ, то х А и х В. Отсюда следует, что х А и х ВС, то есть х А(ВС). Если же х АС, то х А и х С. Отсюда вытекает, что х А и х ВС, то есть х А(ВС). Таким образом, (AB)(AC) A(BC). Следовательно, A(BC) = (AB)(AC). Что и требовалось доказать.

При доказательстве достаточности мы получили, что АВ=. Очевидно, что С, поэтому соотношение доказано. При доказательстве был рассмотрен самый общий случай. Однако здесь возможны ещё некоторые варианты при построении диаграмм. Например, случай равенства АВ=С либо
, случай пустых множества и так далее. Очевидно, что все возможные варианты учесть бывает затруднительно. Поэтому считается, что доказательство соотношений с помощью диаграмм не всегда является корректным.

2. Доказательство с помощью определения равенства множеств.

Необходимость. Пусть АВС и элемент х А. Покажем, что в этом случае элемент множества А будет являться также и элементом множества
.

Рассмотрим два случая: х В или
.

Если х В, то х АВС, то есть х С, и, как следствие этого,
.

Если же
, то и
. Необходимость доказана.

Пусть теперь
их АВ. Покажем, что элемент х также будет элементом множества С.

Если х АВ, тогда х А и х В. Поскольку
, значитх С. Достаточность доказана.

1. Доказательство с помощью диаграммы:

2. Доказательство с помощью определения равенства множеств.

Пусть АВ. Рассмотрим элемент х В (или
). Аналогично:х А (или х Ā). То есть всякий элемент множества есть также элементом множества Ā. А это может быть в случае, если
. Что и требовалось доказать.

Задача 3.4. Выразить символически указанные области и упростить полученные выражения.

Решение.

Искомая область состоит из двух изолированных частей. Условно назовём их верхней и нижней. Множество, которое они изображают, можно описать так:

М = {x  x A и х В и х С или х С и х А и х В}.

Из определения операций над множествами получим:

М = ((АВ)\С)(С\А\В).

Запишем это выражение с помощью основных операций – дополнения, объединения и пересечения:

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

Данную область можно рассматривать как объединение множеств А\В\С и АВС. По определению M = {x  x A и x В и х С или х А и х В и х С}. Упростим:

Задачи для самостоятельного решения.

1. Упростить:

2. Доказать с помощью диаграмм, законов алгебры множеств и определения равенства множеств:

(АВ)\В = А\В;

А(ВС) = А\(А\В)(А\С);

АВ = АВ  А=В;

А\В =   АВ = А.

3. Выяснить, существует ли множество Х, удовлетворяющее при любом А равенству:

АХ = А; (ответ );

Формулы и законы логики

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

НЕ запомнить, НЕ распечатать, а именно ещё раз осмыслить и собственноручно переписать на бумагу – чтобы они были перед глазами:

– таблица НЕ;
– таблица И;
– таблица ИЛИ;
– импликационная таблица;
– таблица эквиваленции.

Это очень важно. В принципе, их было бы удобно занумеровать «Таблица 1», «Таблица 2» и т.д. , но я неоднократно подчёркивал изъян такого подхода – как говорится, в одном источнике таблица окажется первой, а в другом – сто первой. Поэтому будем использовать «натуральные» названия. Продолжаем:

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

1) любые элементарные (простые) высказывания ;

2) если и – формулы, то формулами также являются выражения вида
.

Никаких других формул нет.

В частности формулой является любая логическая операция, например логическое умножение . Обратите внимание на второй пункт – он позволяет рекурсивным образом «создать» сколь угодно длинную формулу. Поскольку – формулы, то – тоже формула; так как и – формулы, то – тоже формула и т.д. Любое элементарное высказывание (опять же согласно определению) может входить в формулу неоднократно.

Формулой не является, например, запись – и здесь прослеживается очевидная аналогия с «алгебраическим мусором» , из которого не понятно – нужно ли числа складывать или умножать.

Логическую формулу можно рассматривать, как логическую функцию . Запишем в функциональном виде ту же конъюнкцию:


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

Таблица, описывающая логическую формулу (функцию) называется, как уже было озвучено, таблицей истинности . Пожалуйста – знакомая картинка:

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

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

– в первую очередь выполняется отрицание ;
– во вторую очередь – конъюнкция ;
– затем – дизъюнкция ;
– потом импликация ;
– и, наконец, низший приоритет имеет эквиваленция .

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

Порядок действий можно изменить привычным способом – скобками:
– здесь в первую очередь выполняется дизъюнкция и только потом более «сильная» операция.

Наверное, все понимают, но на всякий пожарный : и – это две разные формулы! (как в формальном, так и в содержательном плане)

Составим таблицу истинности для формулы . В данную формулу входят два элементарных высказывания и «на входе» нам нужно перечислить все возможные комбинации единиц и нулей. Чтобы избежать путаницы и разночтений договоримся перечислять комбинации строго в таком порядке (который я, собственно, де-факто использую с самого начала) :

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

На втором шаге смотрим на столбцы и и применяем к ним операцию ИЛИ . Немного забегая вперёд, скажу, что дизъюнкция перестановочна ( и – это одно и то же) , и поэтому столбцы можно анализировать в привычном порядке – слева направо. При выполнении логического сложения удобно использовать следующее прикладное рассуждение: «Если два нуля – ставим ноль, если хотя бы одна единица – единицу» :

Таблица истинности построена. А теперь вспомним старую-добрую импликацию:

…внимательно-внимательно… смотрим на итоговые колонки…. В алгебре высказываний такие формулы называются равносильными или тождественными :

(три горизонтальные чёрточки – это значок тождества)

В 1-й части урока я обещал выразить импликацию через базовые логические операции, и выполнение обещания не заставило себя ждать! Желающие могут вложить в импликацию содержательный смысл (например, «Если идёт дождь, то на улице сыро») и самостоятельно проанализировать равносильное утверждение .

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

Задание 1

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

Ещё раз повторим порядок решения задачи:

1) Так как в формулу входят две переменные, то всего будет 4 возможных набора нулей и единиц. Записываем их в оговорённом выше порядке.

2) Импликации «слабее» конъюнкции, но они располагаются в скобках. Заполняем столбец , при этом удобно использовать следующее прикладное рассуждение: «если из единицы следует ноль, то ставим ноль, во всех других случаях – единицу» . Далее заполняем столбец для импликации , и при этом, внимание! – столбцы и следует анализировать «справа налево»!

3) И на завершающем этапе заполняем итоговый столбец . А здесь удобно рассуждать так: «если в столбцах и две единицы, то ставим единицу, во всех остальных случаях – ноль» .

И, наконец, сверяемся с таблицей истинности эквиваленции .

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

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

Коммутативность конъюнкции и коммутативность дизъюнкции

Коммутативность – это перестановочность:


Знакомые с 1-го класса правила: «От перестановки множителей (слагаемых) произведение (сумма) не меняется» . Но при всей кажущейся элементарности этого свойства, справедливо оно далеко не всегда, в частности, некоммутативным является умножение матриц (в общем случае их переставлять нельзя) , а векторное произведение векторов – антикоммутативно (перестановка векторов влечёт за собой смену знака) .

И, кроме того, здесь я снова хочу подчеркнуть формализм математической логики. Так, например, фразы «Студент сдал экзамен и выпил» и «Студент выпил и сдал экзамен» различны с содержательной точки зрения, но неразличимы с позиций формальной истинности. …Таких студентов знает каждый из нас, и из этических соображений мы не будет озвучивать конкретных имён =)

Ассоциативность логического умножения и сложения

Или, если «по-школьному» – сочетательное свойство:


Дистрибутивные свойства

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

И опять же – эти, казалось бы, «банальные» свойства выполняются далеко не во всех алгебраических системах, и, более того, требуют доказательства (о которых мы очень скоро поговорим) . К слову, второй дистрибутивный закон несправедлив даже в нашей «обычной» алгебре. И в самом деле:

Закон идемпотентности

Что делать, латынь....


Прямо какой-то принцип здоровой психики: «я и я – это я», «я или я – это тоже я» =)

И тут же несколько похожих тождеств:


…мда, что-то я даже подзавис… так и доктором философии завтра можно проснуться =)

Закон двойного отрицания

Ну а здесь уже напрашивается пример с русским языком – все прекрасно знают, что две частицы «не» означают «да». А для того, чтобы усилить эмоциональную окраску отрицания нередко используют три «не»:
– даже с крохотным доказательством получилось!

Законы поглощения

– «а был ли мальчик?» =)

В правом тождестве скобки можно опустить.

Законы де Моргана

Предположим, что строгий Преподаватель (имя которого вам тоже известно:)) ставит экзамен, если – Студент ответил на 1-й вопрос и – Студент ответил на 2-й вопрос . Тогда высказывание , гласящее о том, что Студент не сдал экзамен , будет равносильно утверждению – Студент не ответил на 1-й вопрос или на 2-й вопрос .

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

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

В результате «на выходе» получена формула, истинность которой совпадает с истинностью высказывания . Равносильность доказана.

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

Теперь убедимся, например, в справедливости закона де Моргана .

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

Далее составим таблицу истинности для правой части . Здесь тоже всё прозрачно – в первую очередь проводим более «сильные» отрицания, затем применяем к столбцам правило И :

Результаты совпали, таким образом, тождество доказано.

Любую равносильность можно представить в виде тождественно истинной формулы . Это значит, что ПРИ ЛЮБОМ исходном наборе нулей и единиц «на выходе» получается строго единица. И этому есть очень простое объяснение: так как таблицы истинности и совпадают, то, разумеется, они эквивалентны.Соединим, например, эквиваленцией левую и правую часть только что доказанного тождества де Моргана:

Или, если компактнее:

Задание 2

Доказать следующие равносильности:

б)

Краткое решение в конце урока. Не ленимся! Постарайтесь не просто составить таблицы истинности, но ещё и чётко сформулировать выводы. Как я недавно отмечал, пренебрежение простыми вещами может обойтись очень и очень дорого!

Продолжаем знакомиться с законами логики!

Да, совершенно верно – мы с ними уже вовсю работаем:

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

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

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

Фирменный пример противоречия от древних греков:
– никакое высказывание не может быть истинным и ложным одновременно.

Доказательство тривиально:

«На выходе» получены исключительно нули, следовательно, формула действительно тождественна ложна .

Однако и любое противоречие – это тоже закон логики, в частности:

Нельзя объять столь обширную тему в одной-единственной статье, и поэтому я ограничусь ещё лишь несколькими законами:

Закон исключённого третьего

– в классической логике любое высказывание истинно или ложно и третьего не дано. «Быть или не быть» – вот в чём вопрос.

Самостоятельно составьте табличку истинности и убедитесь в том, что это тождественно истинная формула.

Закон контрапозиции

Этот закон активно муссировался, когда мы обсуждали суть необходимого условия , вспоминаем: «Если во время дождя на улице сыро, то из этого следует, что если на улице сухо, то дождя точно не было» .

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

Если истинна обратная теорема , то в силу закона контрапозиции , справедлива и теорема, противоположная обратной :

И снова вернёмся к нашим содержательным примерам: для высказываний – число делится на 4, – число делится на 2 справедливы прямая и противоположная теоремы, но ложны обратная и противоположная обратной теоремы. Для «взрослой» же формулировки теоремы Пифагора истинны все 4 «направления».

Закон силлогизма

Тоже классика жанра: «Все дубы – деревья, все деревья – растения, следовательно, все дубы – растения» .

Ну и здесь опять хочется отметить формализм математической логики: если наш строгий Преподаватель думает, что некий Студент – есть дуб, то с формальной точки зрения данный Студент, безусловно, растение =) …хотя, если задуматься, то может быть и с неформальной тоже =)

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

1) выполняем импликации и . Вообще говоря, можно сразу выполнить и 3-ю импликацию, но с ней удобнее (и допустимо!) разобраться чуть позже;

2) к столбцам применяем правило И ;

3) вот теперь выполняем ;

4) и на завершающем шаге применяем импликацию к столбцам и .

Не стесняйтесь контролировать процесс указательным и средним пальцем:))


Из последнего столбца, думаю, всё понятно без комментариев:
, что и требовалось доказать.

Задание 3

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


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

Преобразование логических формул

Помимо своего «логического» назначения, равносильности широко используются для преобразования и упрощения формул. Грубо говоря, одну часть тождества можно менять на другую. Так, например, если в логической формуле вам встретился фрагмент , то по закону идемпотентности вместо него можно (и нужно) записать просто . Если вы видите , то по закону поглощения упрощайте запись до . И так далее.

Кроме того, есть ещё одна важная вещь: тождества справедливы не только для элементарных высказываний, но и для произвольных формул. Так, например:



, где – любые (сколь угодно сложные) формулы.

Преобразуем, например, сложную импликацию (1-е тождество) :


Далее применим к скобке «сложный» закон де Моргана, при этом, в силу приоритета операций, именно закон , где :


Скобки можно убрать, т.к. внутри находится более «сильная» конъюнкция:


Ну, а с коммутативностью вообще всё просто – даже обозначать ничего не нужно… что-то запал мне в душу закон силлогизма:))


Таким образом, закон можно переписать и в более затейливом виде:


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

В качестве тренировки упросим формулу .

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

Как правило, на первом шаге (шагах) избавляются от эквиваленции и импликации (если они есть) и сводят формулу к трём основным логическим операциям. Что тут скажешь…. Логично.

(1) Используем тождество . А нашем случае .

Затем обычно следуют «разборки» со скобками. Сначала всё решение, затем комментарии. Чтобы не получилось «масло масляное», буду использовать значки «обычного» равенства:


(2) К внешним скобкам применяем закон де Моргана , где .

Законы де Моргана – это логические правила, установленные шотландским математиком Огастесом де Морганом, связывающие пары логических операций при помощи логического отрицания.

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

not (А and В) = (not А) or (not В)

not (А or В) = (not А) and (not В)

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



Законы де Моргана можно сформулировать следующим образом:

I закон де Моргана: Отрицание дизъюнкции двух простых высказываний равносильно конъюнкции отрицаний этих высказываний.

II закон де Моргана: Отрицание конъюнкции двух простых высказываний равносильно дизъюнкции отрицаний этих высказываний.

Рассмотрим применение законов де Моргана на конкретных примерах.

Пример 1. Преобразовать формулу так, чтобы не было отрицаний сложных высказываний.

Воспользуемся первым законом де Моргана, получим:

к отрицанию конъюнкции простых высказываний В и С применим второй закон де Моргана, получим:

,

таким образом:

.

В итоге мы получили равносильное высказывание, в котором нет отрицаний составных высказываний, а все отрицания относятся только к простым высказываниям.

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

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

.

Таблица 1.

			В/\С	А\/В/\С



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

Теорема поглощения записывается в двух формах - дизъюнктивной и

конъюнктивной, соответственно:

А +АВ =А (16)

А(А + В)=А (17)

Докажем первую теорему. Вынесем за скобки букву А:

А + АВ= А(1 + В)

Согласно теореме (3) 1 + В = 1, следовательно

А(1 + В) = А 1 = А

Чтобы доказать вторую теорему, раскроем скобки:

А(А + В) = А А + АВ = А + АВ

Получилось выражение, только что доказанное.

Рассмотрим несколько примеров на применение теоремы поглощения при

упрощении булевых формул.

Теорема склеивания также имеет две формы - дизъюнктивную и

конъюнктивную:

Докажем первую теорему:

поскольку согласно теоремам (5) и (4)



Для доказательства второй теоремы раскроем скобки:



Согласно теореме (6) следовательно:

По теореме поглощения (16) А+АВ = А

Теорема поглощения, как и теорема склеивания, применяется при упрощении

булевых формул, например:



Теорема де Моргана связывает все три основные операции булевой алгебры

Дизъюнкцию, конъюнкцию и инверсию:

Первая теорема читается так: инверсия конъюнкции есть дизъюнкция

инверсий. Вторая: инверсия дизъюнкции есть конъюнкция инверсий. Доказать теоремы Моргана можно с помощью таблиц истинности для левой и правой частей.

Теорема де Моргана применима и к большему числу переменных:

Лекция 5

Инвертирование сложных выражений

Теорема де Моргана применима не только к отдельным конъюнкциям

или дизъюнкциям, но и к более сложным выражениям.

Найдем инверсию выражения АВ + CD , представленного в виде дизъюнкции конъюнкций. Инвертирование будем считать законченным, если знаки отрицания стоят только над переменными. Введем обозначения: АВ = Х;

CD = Y, тогда

Найдем и подставим в выражение (22):



Таким образом:

Рассмотрим выражение, представленное в конъюнктивной форме:

(А + В)(С + D)

Найдем его инверсию в виде



Введем обозначения: А + В = X; С + D =Y, тогда

Найдем и подставим их в выражение

Таким образом:

При инвертировании сложных выражений можно пользоваться следующим правилом. Чтобы найти инверсию, необходимо знаки конъюнкции заменить знаками дизъюнкции, а знаки дизъюнкции - знаками конъюнкции и поставить инверсии над каждой переменной:

Понятие булевой функции

В общем случае функция (лат. functio - исполнение, соответствие,

отображение) - это некоторое правило (закон), согласно которому каждому элементу множества X, представляющего собой область значений независимого переменного х, ставится в соответствие определенный элемент множества F,

под которым понимается область значений зависимого переменного f . В случае булевых функций X = F = {0,1}. Правилом, при помощи которого задается функция, может служить любая булева формула, например:



Символом f здесь обозначена функция, которая является, как и аргументы А, В, С, двоичной переменной.

Аргументы - это независимые переменные, они могут принимать любые значения - либо 0, либо 1. Функция же f - зависимая переменная. Ее значение полностью определяется значениями переменных и логическими связями между ними.

Главная особенность функции: чтобы определить ее значение, в общем случае необходимо знать значения всех аргументов, от которых она зависит. Например, приведенная выше функция зависит от трех аргументов А, В, С. Если принять А = 1, то получим



т. е. получилось новое выражение, не равное ни нулю, ни

единице. Пусть теперь В = 1. Тогда



т. е. и в этом случае неизвестно, чему равна функция, нулю или единице.

Примем, наконец, С = 0. Тогда получим: f = 0. Таким образом, если в исходном выражении принять А = 1, В = 1, С= 0, то функция примет нулевое значение: f = 0.

Рассмотрим понятие набора значений переменных .

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

называть просто набором. Набор значений аргументов - это последовательность нулей и единиц, например, 110, где первая цифра соответствует первому аргументу, вторая - второму и третья - третьему. Очевидно, что необходимо заранее договориться, что такое первый, второй или, допустим, пятый аргумент. Для этого удобно пользоваться алфавитным расположением букв.

Например, если

то согласно латинскому алфавиту первым является аргумент Р, вторым -

Q, третьим - X, четвертым - У. Тогда по набору значений аргументов легко

найти значение функции. Пусть, например, дан набор 1001. Согласно его

записи т. е. на наборе 1001 заданная функция равна единице.

Еще раз отметим, что набор значений аргументов - это совокупность

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

Отсюда возникает вопрос - нельзя ли наборы рассматривать как двоичные

числа? Можно, и во многих случаях это очень удобно, особенно если двоичное

число перевести в десятичную систему. Например, если

А = 0, В = 1, С = 1, D= 0,

0 * 2 3 +1 * 2 2 +1 * 2 1 +0 * 2 0 = 4+2 = 6

т. е. заданный набор имеет номер 6 в десятичной системе.

Если по десятичному номеру требуется найти значения аргументов, то

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

Пусть, например, требуется найти значения аргументов А, В, С, D, Е, F по набору с номером 23. Переводим число 23 в двоичную систему методом

деления на два:

В результате получаем 23 10 = 10111 2 . Это число пятизначное, а всего

аргументов шесть, следовательно, слева необходимо записать один нуль:

23 10 = 010111 2 . Отсюда находим:

А = 0, В = 1, С = 0, D = 1, Е = 1, F = 1.

Сколько всего существует наборов, если известно число п аргументов? Очевидно, столько же, сколько существует n-разрядных двоичных чисел, т. е. 2 n

Лекция 6

Задание булевой функции

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

На примере функции



выясним, как построить для нее таблицу соответствия.

Функция зависит от трех аргументов А, В, С. Следовательно, в таблице

предусматриваем три колонки для аргументов A,B,C и одну колонку для значений функции f. Слева от колонки А полезно разместить еще одну колонку. В ней будем записывать десятичные числа, которые соответствуют наборам, если их рассматривать как трехразрядные двоичные номера. Эта десятичная

колонка вводится для удобства работы с таблицей, поэтому, в принципе,

ею можно пренебречь.



Заполняем таблицу. В строке с номером ООО записано:

А = В = С = 0.

Определим значение функции на этом наборе:

В колонке f записываем нуль в строке с набором 000.

Следующий набор: 001, т. е. А = В = 0, С = 1. Находим значение функции

на этом наборе:

На наборе 001 функция равна 1, следовательно, в колонке f в строке с

номером 001 записываем единицу.

Аналогично вычисляем значения функций на всех остальных наборах и

заполняем всю таблицу.