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

В алгебре логики переменные могут принимать только 2 значения:
0 или 1.
Табл.1.1 Табл.1.2
------------T------------¬ -----------T---------¬
¦Аргументы ¦ Функции ¦ ¦Аргументы ¦ Функция¦
+-----------+------T-----+ +----------+---------+
¦ ¦ И ¦ ИЛИ¦ ¦ ¦ НЕ ¦
¦ х1 х2 +------+-----+ ¦ х +---------+
¦ ¦ у1¦ у2¦ ¦ ¦ у3 ¦
+-----------+------+-----+ +----------+---------+
¦ 0 0 ¦ 0 ¦ 0 ¦ ¦ 0 ¦ 1 ¦
¦ 0 1 ¦ 0 ¦ 1 ¦ +----------+---------+
¦ 1 0 ¦ 0 ¦ 1 ¦ ¦ 1 ¦ 0 ¦
¦ 1 1 ¦ 1 ¦ 1 ¦ L----------+---------+
+-----------+------+------
И -логическое умножение,конъюкция.
ИЛИ -логическое сложение,дизъюнкция.
НЕ -отрицание,инверсия.

Графическое и аналитическое представление основных логических
функций приведено на рисунке 1.1.
------¬ ------¬ __
X1--+ & ¦ X1--+ 1 о--У3=Х1
Х2--+ +--У1=Х1*Х2 L------
L------
------¬
X1--+ 1 ¦
X2--+ +--Y2=X1+X2 Рис.1.1
L------

У1=Х1*Х2=Х1&X2=Х1Х2=X1 ^ X2

У2=Х1+Х2=Х1VХ2
_
У3=Х
Далее в качестве знака отрицания вместо "крышки" будет использо-
ваться апостроф.
Для n переменных в двоичной логике имеется 2^2^n функций.Полный
набор логических функций от 2-х переменных представлен в табл.1.3.
Табл.1.3
-----T---T---T---T---T---T---T---T---T---T---T---T---T---T---T---T---¬
¦ xy ¦z0 ¦z1 ¦z2 ¦z3 ¦z4 ¦z5 ¦z6 ¦z7 ¦z8 ¦z9 ¦z10¦z11¦z12¦z13¦z14¦z15¦
+----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
¦ 00 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦
¦ 01 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦
¦ 10 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦
¦ 11 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦
L----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+----
Некоторые из этих функций получили специальные названия:
z0 = 0 - тождественный нуль;
z1 = xy - конъюнкция;
z6 = xy'+x'y - неравнозначность,сумма по модулю 2;
z7 = x+y - дизъюнкция;
z8 = x'y' = (x+y)' - функция Вебба(стрелка Пирса);
z9 = x'y'+xy - равнозначность;
z13= x'+y= x -> y - импликация,а также Axy;
z14= x'+y' = (xy)' - функция Шеффера,а также Exy;
z15= 1 - тождественная 1,а также Ixy(8).

1.2.Основные законы алгебры Буля.
1. Комплементарность.
a*a'=0; a+a'=1
2. Идемпотентный закон.
а*а=а; а+а=а
3. Переместительный закон.
а+в=в+а; ав=ва
4. Сочетательный закон.
(а+в)+с=а+(в+с); (ав)*с=а*(вс)
5. Закон поглощения.
а+ав=а(1+в)=а; а(а+в)=а+ав=а
6. Распределительный закон.
а(в+с)=ав+ас; (а+в)(а+с)=а+вс
/* (а+в)(а+с)=а*а+ав+ас+вс=(а+ав+ас)+вс=
=а(1+в+с)+вс=а+вс */
7. Закон склеивания
ав+ав'=а(в+в')=а;
(а+в)(а+в')=а+ав+ав'+вв'=а+а(в+в)+0=
=а+а*1=а+а=а
8.Правила де Mоргана.
____ ____
_ _ _ _
а+в = а*в; а*в = а*в
_________ __________
_ _ _ _ _ _
/*а+в+...+z = а*в...*z; а*в*...*z = а+в+...+z */

Заучивать все логические законы и запоминать их названия нет ни-
какого смысла,тем более,что на практике используются 2-3 из них(законы
поглощения и склеивания,правила Де Моргана).Значительно важнее осмыс-
лить эти законы и научиться применять.
С помощью правил де Моргана легко реализуются логические схемы на
базе интегральных схем(ИС) так называемого функционально полного бази-
са(ФПБ).ФПБ характерен тем,что на его основе можно построить любую
сколь угодно сложную схему,в том числе и самую сложную вычислительную
машину без применения других ИС.К ФПБ относятся ИС типа И-НЕ,а также
ИЛИ-НЕ.Таким образом,на очень простом элементе типа И-НЕ может быть
построена,например,сложная система управления ракетой.Только в этой
системе управления простые элементы И-НЕ сгруппированы в большие ин-
тегральне схемы(БИС),которые выполняют функции процессора,памяти и то-
му подобных сложных устройств.
Пусть нам необходимо построить схему,реализующую функцию
y = x1x2 + x3x4.Используя формулу де Моргана,получим следующее соотно-
шение:
y = x1x2 + x3x4 = ((x1x2)'(x3x4)')'.
Таким образом,мы выразили исходную функцию с помощью одних только
элементов И-НЕ.Схема реализации заданной функции представлена на ри-
сунке.

------¬
X1--+ & ¦ (x1x2)'
Х2--+ о-------¬ ------¬
L------ L-------+ & ¦ y=((x1x2)'(x3x4)')'=x1x2+x3x4
--------+ о--
------¬ ¦ L------
X3--+ & ¦ ¦
Х4--+ о--------
L------ (x3x4)'

Синтез релейных схем выполняется также на основе алгебры логики.
3.Задача.
Задержаны подозреваемые в преступлении Браун,Джон и Смит.Один из
них говорит правду,другой - полуправду,третий - ложь.Приведем их пока-
зания.
Браун:"Я совершил это,Джон не виноват."
Джон:"Браун не виноват,преступник - Смит."
Смит:"Я не виноват,виноват Браун."
Найти преступника,если известно,что он один.
Решение.
Введем обозначения:
B - виноват Браун;
C - виноват Смит;
D - виноват Джон.
Тогда условие задачи будет выражено двумя уравнениями:
1)BD'+B'C+BC' = 1(показания подозреваемых,одно из них истинно);
2)B'C'+B'D'+C'D' = 1(преступник единственный).
M = (BD'+B'C+BC')(B'C'+B'D'+C'D') = B'CD'+BC'D' = 1.
BC'D' отпадает,т.к. иначе Браун и Смит оба говорят правду.Следо-
вательно,истинно B'CD',т.е. преступник - Смит,он еще и лжец.Джон гово-
рит правду,Браун - полуправду.Кстати,отсеять BC'D' можно было на пер-
вом этапе,поскольку из условий задачи следует BD'+BC' = 0,поэтому
M = B'C(B'C'+B'D'+C'D') = B'CD'.
4.Задача.
Если в экспедицию поедет Арбузов,то поедут и Брюквин с Вишневс-
ким.Если поедут Арбузов с Вишневским,то поедет и Брюквин.Кто отправит-
ся в экспедицию?
Решение.
A - поедет Арбузов.
B - поедет Брюквин.
W - поедет Вишневский.
1)A -> (B+W);
2)AW -> B.
M = (A'+B+W)(A'+W'+B) = A'+B = A -> B,т.е. если поедет Арбузов,то
поедет и Брюквин.