Булева алгебра

Так как здание всего мира совершенно и возведено премудрым Творцом, то в мире не происходит ничего, в чем не было бы виден смысл какого-нибудь максимума или минимума.

Эйлер

Булевой алгеброй называется дистрибутивная структура с неравными друг другу единицей 1 и нулем 0, в которой всякий элемент имеет дополнение. Булева алгебра всегда содержит не менее двух элементов. Алгебра, содержащая только 1 и 0, называется вырожденной.

Основные логические функции

Обозначим через E₂ = {0, 1} – множество, состоящее из двух чисел. Числа 0 и 1 являются основными в дискретной математике. Часто они интерпретируются как “ложь” (л = {0}) и как “истина” (и = {1}).

Декартово произведение E Е Е … E = Eⁿ является множеством упорядоченных наборов, состоящих из п чисел (нулей и единиц). Как известно, Е^п cодержит 2^п элементов (упорядоченных наборов). Само множество Е^п можно естественным образом упорядочить, для чего достаточно считать каждый набор двоичным разложением целого числа k, записанного с помощью п знаков. Упорядочение наборов проводится по числу k .

Например, при п = 3 множество Е³ может быть упорядочено следующим образом.

0	1	2	3	4	5	6	7
000	001	010	011	100	101	110	111

Такое упорядочение еще называют “скользящей единицей”.

Этот естественный порядок элементов Е^п является самым распространенным, но иногда удобен другой способ упорядочения.

Логической (булевой) функцией (или просто функцией) n переменных

y = f(x₁, x₂, …, x_n)

называется такая функция, у которой все переменные и сама функция могут принимать только два значения: 0 и 1.

Переменные, которые могут принимать только два значения 0 и 1 называются логическими переменными (или просто переменными). Заметим, что логическая переменная х может подразумевать под числом 0 некоторое высказывание, которое ложно, и под числом 1 высказывание, которое истинно.

Пример.

Высказывание “Москва находится в Европе” является истинным и, значит, с точки зрения дискретной математики принимает значение 1.

Высказывание “в сутках 27 часов” является ложным, и переменная, которая заменяет это высказывание, принимает значение 0.

Имеется много высказываний, которые либо истинны, либо ложны, но о которых мы не знаем, что имеет место на самом деле. Например, высказывание “студент Петров (имеется в виду конкретный человек) имеет дома компьютер”. Такого рода высказывания требуют проверки (конечно, если нам важен этот факт). Поэтому считаем, что переменная, заменяющая это высказывание может принимать значение 0 или 1.

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

Пример.

Функция трех переменных f(x,y,z) может определяться следующей таблицей истинности.

x	0	0	0	0	1	1	1	1
y	0	0	1	1	0	0	1	1
z	0	1	0	1	0	1	0	1
f(x,y,z)	1	0	1	1	0	1	0	0

Это означает, что f(0,0,0) = 1, f(0,0,1) = 0, f(0,1,0) = 1 и т. д.

Две функции равны, если совпадают их таблицы истинности (на объединенном наборе переменных).

При таком задании наборы Е^п всегда упорядочены естественным образом, это позволяет определять функцию только последним столбцом (который иногда для экономии места записывается в строчку). Например, в нашем примере функцию f(x,y,z) можно задать так: f = (10110100), это означает, что последний столбец таблицы истинности

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

Теперь можно описать основные функции дискретной математики.

Булева функция.

Булевой функцией от n аргументов x₁, x₂, … ,x_n, называется функция f из n-ой степени множества {0, 1} в множество {0, 1} f: {0,1}ⁿ .→ {0,1}, т.е. функция, которая произвольному набору из нулей и единиц ставит в соответствие значение функции f(δ₁, δ₂, … ,δ_n){0,1}.

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

Булевой функцией описываются преобразования некоторым устройством входных сигналов в выходные. Пусть устройство f имеет n входов x₁, x₂, … ,x_n на которые может подаваться (1) или не подаваться (0) ток и один выход, на котором ток есть (1) или (0). Таким образом, значение переменной x_i = 1 интерпретируется как поступление тока на i-й вход, а x_i = 0 - как не поступлении тока. Значение на выходе устройства f(δ₁, δ₂, … ,δ_n) = 1, означает ток на выходе при заданном входе и f(δ₁, δ₂, … ,δ_n) = 0 - тока на выходе нет.

Иначе говоря, булева функция – это функция, и аргументы и значение которой принадлежит множеству {0, 1}. Множество {0, 1} мы будем в дальнейшем обозначать через B.

Булеву функцию от nаргументов можно рассматривать какn-местную алгебраическую операцию на множествеB. При этом алгебра<B;W>, гдеW– множество всевозможных булевых функций, называетсяалгеброй логики.

В дискретной математике большую роль играют конечные функции.

Конечной функцией называют отображение одного конечного множества в другое.

Важный класс таких функций образуют булевы функции.

Булева функция (от n переменных) - это произвольное отображение вида

f: Bⁿ → B, B={0,1};

Булева функция определена на множестве всех n-элементных последовательностей (n-элементных кортежей) нулей и единиц и принимает два возможных значения: 0 и 1.

Булева константа - это индивидная константа с областью значений {0,1}. Таким образом, существует две булевы константы: 0 и 1. По определению принимается, что каждая булева константа есть также булева функция от 0 переменных (нульарная операция).

Булево переменное - это индивидное переменное с областью значений {0,1}, т.е. это переменное, которое может принимать только два значения: 0 и 1.

Тогда булева функция f: {0,1}ⁿ → {0,1} задается y = f(x₁, . . . , x_n), в которой каждое булево переменное x_i (i = 1, . . .,n) и функция f принимают два возможных значения: 0 и 1.

Переменные x₁, . . . , x_n называют - переменными булевой функции f.

Кортеж из множества {0,1}ⁿ называется набором значений переменных x₁, . . . , x_n . Мощность этого множества 2ⁿ

Число функции f: M → N равно N^M (2 в степени 2ⁿ )

Булевой функции можно придать другой смысл.

1 – истина

0 – ложь

Тогда из простых высказываний можно составить сложное.

Алгебра логики - множество высказываний и операций - одной унарной и 4 бинарных:

А₁ = ‹b, {, , , → , ~}›

: {0,1} → {0,1} - отрицание

: {0,1}² → {0,1} - конъюнкция (лог. умножение) – "и"

: {0,1}² → {0,1}- дизъюнкция (лог. сложение) - "или"

Или 1 – включено, 0 - выключено.

Тогда получаем переключательную функцию или двоичную функцию

Примеры

Параллельное и последовательное соединения

Двоичное дерево

Двухэлементная булева алгебра.

Рассмотрим множество В_о = {0,1} и определим на нем операции , согласно таблицам истинности формул , , .

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

По теореме о функциональной полноте в булевой алгебре B_о с помощью терма можно задать любую булеву функцию.

Функции одной переменной y = f(x)

Существует четыре различных функции одной переменной на множестве {0,1}: константа "0", константа "1", переменная x и инверсия переменной x (). Нетрудно убедиться, что из этих функций с помощью операций суперпозиции и подстановки можно получить только функцию одной переменной.

Перенумеруем эти функции (их 4) естественным образом и расположим в виде таблицы:

x	f0	f1	f2	f3
0	0	0	1	1
1	0	1	0	1

Видно, что f₀ (х) = 0, a f₃ (х) = 1, т. е. эти две функции не зависят от х, f₁ (х) = х, т.е. она не меняет аргумента. Функция f₂ (х) действительно содержательная функция. Она принимает значения, противоположные значениям аргумента, обозначается f₂ (х) = и называется отрицанием (применяют еще обозначение x (читается “не x”)).

Отрицанием высказывания X называется высказывание , которое истинно, когда X ложно, и ложно, когда X истинно.

Таблица истинности для отрицания

X
0	1
1	0

Таблицы булевых функций

Булева функция от n переменных может быть задана таблицей, состоящей из двух столбцов и 2ⁿ строк. В первом столбце перечисляются все наборы из Bⁿ в лексикографическом порядке, а во втором – значения функции на наборах.

При n = 1 имеем 4 булевых функции

x	f1(x)	f2(x)	f3(x)	f4(x)
0 1	0 1	0 0	1 1	1 0

f₁(x) - тождественная функция

f₂(x) - константа 0

f₃(x) - константа 1

f₄(x) - отрицание

Функции двух переменных z = f(x,y).

Различных функций двух переменных существует уже шестнадцать. Эти функции, их названия и обозначения приведены в табл. 1. Число этих функций равно 2⁴ = 16. Перенумеруем и расположим их тоже в естественном порядке.

При n = 2 имеем 16 булевых функции

x1	x2	f0	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15
		0										y	yx	x	xy		1
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₀ - константа 0.

f₁ – конъюнкция f₁ = xy ( x&y; xy)

f₂ – запрет по y

f₃ – повторение по x

f₄ – запрет по x

f₅ – повторение по y

f₆ – сумма по модулю 2

f₇ – дизъюнкция

f₈ – стрелка Пирса

f₉ – эквивалентность

f₁₀ – отрицание y

f₁₁ – импликация от y к x

f₁₂ – отрицание x

f₁₃ – импликация от x к y

f₁₄ – штрих Шеффера

f₁₅ - константа 1.

Для инженера ВТ алгебра логики (ВТ – алгебра переключательных схем или комбинационная логика) является системой алгебраических методов решения логических задач, а также совокупных задач, решаемых такими методами; для ВТ - это инструмент синтеза комбинационных схем, являющихся частным случаем конечных ????, элементной базой которого является либо функциональные элементы,

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

(упрощение, минимизация) с целью алгоритмизации решения задач.

В алгебре логики высказывания рассматриваются только с точки зрения истинности или ложности без рассматривания их смысла.

Индекс функции f_i(x, y) является десятичным эквивалентом двоичного числа, образованного из вектора значений функции на упорядоченном множестве наборов значений аргументов: {(0,0),(0,1),(1,0),(1,1)}. Функции f₀, f₃, f₅, f₁₀, f₁₂, f₁₅ являются расширением на случай двух переменных уже известных функций одной переменной. Функции f₁(x,y) = x ∨ y (конъюнкция) и f₇(x,y) = x ∧ y (дизъюнкция) совместно с функцией инверсии (f₁₀, f₁₂) были использованы в предыдущих разделах для построения форм представления переключательных функций, пригодных для аналитической записи переключательных функций произвольной сложности.

Рассмотрим более подробно эти функции. Две из них f₀ = 0 и f₁₅ = 1 являются константами. Наиболее важные функции двух переменных имеют специальные названия и обозначения. Заметим, что эти обозначения не всегда общеприняты.

Перечислим 7 важнейших функций:

1) конъюнкция (функция И ) двух высказываний X и Y называется высказывание XY, которое истинно только в том случае, когда X и Y оба истинны.

Таблица истинности для конъюнкций

X	Y	XY
0	0	0
0	1	0
1	0	0
1	1	1

Заметим, что конъюнкция – это фактически обычное умножение (нулей и единиц). Иногда эту функцию обозначают X&Y или XY.

2) дизъюнкция (функция ИЛИ ) двух высказываний X и Y называется высказывание XY, которое истинно только в том случае, когда X и Y оба истинны.

Таблица истинности для дизъюнкций

X	Y	XY
0	0	0
0	1	1
1	0	1
1	1	1

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

Таблица истинности для импликации

X	Y	XY
0	0	1
0	1	1
1	0	0
1	1	1

Иногда импликацию обозначают x→y (читается “из x следует y”).

Это очень важная функция, особенно в логике. Ее можно рассматривать следующим образом: если х = 0 (т.е. х “ложно”), то из этого факта можно вывести и “ложь”, и “истину” (и это будет правильно), если у = 1 (т. е. у “истинно”), то истина выводится и из “лжи” и из “истины”, и это тоже правильно. Только вывод “из истины ложь” является неверным. Заметим, что любая теорема всегда фактически содержит эту логическую функцию.

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

Таблица истинности для импликации

X	Y	XY
0	0	0
0	1	1
1	0	1
1	1	0

5) эквивалентность или подобие двух высказываний X и Y называется высказывание XY, которое истинно тогда и только тогда, когда X и Y оба истинны или ложны.

Таблица истинности для эквивалентности

X	Y	XY
0	0	1
0	1	0
1	0	0
1	1	1

Эта f₉ = 1 тогда и только тогда, когда х = у. Заметим, что будем применять оба обозначения: х^у (в основном при изучении функций) и х ~ у (когда речь будет идти о логических операциях).

6) штрих Шеффера двух высказываний X и Y называется высказывание , которое ложно только, когда оба высказывания истины. По определению штрих Шеффера является антиконъюнкцией .

Таблица истинности для штриха Шеффера (антиконъюнкции)

X	Y
0	0	1
0	1	1
1	0	1
1	1	0

Иногда эту функцию называют “не и” (так как она равна отрицанию конъюнкции).

Замечание. Конъюнкция, дизъюнкция, отрицание были определены для объектов, принимающих лишь два значения 0 и 1. Однако бывают случаи, когда можно ввести такие операции для некоторых других объектов (эти операции также называют иногда конъюнкцией, дизъюнкцией и отрицанием), для которых также выполнены свойства 1–6. В этом случае говорят, что на этих объектах введена булева алгебра.

7) стрелка Пирса (иногда эту функцию называют штрих Лукасевича) двух высказываний X и Y называется высказывание , которое истинно только, когда оба высказывания ложны. По определению стрелка Пирса (штрих Лукасевича) является антидизъюнкцией .

Таблица истинности для стрелки Пирса (антидизъюнкцией)

X	Y
0	0	1
0	1	0
1	0	0
1	1	0

Эта функция является отрицанием дизъюнкции и поэтому иногда ее называют “не или”.

Заметим, что свойства последних двух функций (как будет видно далее) похожи между собой и, может быть, поэтому в литературе их часто путают (т. е. называют f₈ штрихом Шеффера, а f₁₄ – стрелкой Пирса).

Замечание. Во всех вышеприведенных таблицах истинности логических операций число строк 2ⁿ, где n – число простых высказываний.

Три оставшиеся функции, (f₂ , f₄ и f₁₁) особого значения в дискретной математике не имеют.

Заметим, что часто будут рассматриваться функции от функций, т. е. суперпозиции перечисленных выше функций. При этом последовательность действий указывается (как обычно) скобками. Исключение составляет конъюнкция (которая на самом деле является обычным умножением в двоичной системе). Поэтому конъюнкция совершается первой, даже если отсутствуют скобки. Например, запись xy yz означает (xy) (yz).

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

Помимо этих связок используются еще три связки полученные из вышеуказанных связок

Название	Прочтение	Обозначение
Штрих Шеффера	Антиконъюнкция
Стрелка Пирса	Антидизъюнкция
Сумма по модулю два	Антиэквивалентность

Штрих Шеффера илиантиконъюнкция, по определению

Стрелка Пирса илиантидизъюнкция, по определению

Сумма по модулю два илиантиэквивалентность, по определению

Таблицы истинности этих операций

X	Y	Штрих Шеффера	Стрелка Пирса	Сумма по модулю 2
0	0	1	1	0
0	1	1	0	1
1	0	1	0	1
1	1	0	0	0

Порядок выполнения операций

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

Соглашения относительно расстановки скобок.

1. Внешние скобки не пишутся.

Пример. Вместо пишут

2. На множестве вводятся транзитивное отношение < «быть более сильным» и отношение эквивалентности ~ «быть равносильным» по правилам показанным на рис.

~ ~

~

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

Конечность области определения функции имеет важное преимущество – такие функции можно задавать перечислением значений при различных значениях аргументов. Для того, чтобы задать значение функции от nпеременных, надо определить значения для каждого из 2ⁿнаборов. Эти значения записывают в таблицу в порядке соответствующих двоичных чисел. В результате получается таблица следующего вида:

Булева функция f(x₁, x₂, … ,x_n) полностью определяется своей таблицей истинности

x1	x2	x3	…	xn-1	xn	f(x1, x2, … ,xn)
0	0	0	…	0	0	f(0, 0, … 0, 0)
0	0	0	…	0	1	f(0, 0, … 0, 1)
. . .	. . .	. . .	… … …	. . .	. . .	. . .
1	1	1	…	1	0	f(1, 1, … 1, 0)
1	1	1	…	1	1	f(1, 1, … 1, 1)

В каждой строке таблицы истинности задается набор значений переменных (δ₁, δ₂, … ,δ_n), а затем - значение функции на этом наборе.

Если булева функция f и формула φ имеют одну и ту же таблицу истинности, то формула φ представляет функцию f.

Эквивалентность формул

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

Формулы φ(x₁,..., x_n) и ψ(x₁,..., x_n) называются эквивалентными (φ ~ ψ), если совпадают их таблицы истинности, т. е. совпадают представляемые этими формулами функции f_φ(x₁,..., x_n) и f_ψ(x₁,..., x_n)

Пример 1. Проверка на эквивалентность следующих формул и. Построим таблицы истинности формули,

x	y
0	0	1	1
0	1	1	1
1	0	0	0
1	1	1	1

убеждаемся в том, что ~. Действительно это отношение ~ является отношением эквивалентности, т. е. оно рефлексивно (φ ~ φ), симметрично (φ ~ ψ) => (ψ ~ φ) и транзитивно (φ ~ ψ, ψ ~ χ => φ ~ χ).

Основные эквивалентности между формулами:

1. ~;~-(ассоциативность и).

2. ~;~-(коммутативность и).

3. ~φ; ~φ - (идемпотентность и).

4. ~;~-(законы дистрибутивности и).

5. ~φ; ~φ - (законы поглощения и).

6. ~;~-(законы де Моргана).

7. ~φ; - (закон двойного отрицания - инволютивность).

8. ~;

9. ~;

10. ~;~;

11. ~φψ; ~φψ.

11. Закон склеивания: .

12. Для функций: конъюнкция, дизъюнкция и сумма по модулю два справедливы следующие тождества:

; ; ;

; ; ;

; ; ;

; ; ;

13. Для функций конъюнкция и дизъюнкция справедливы тожде­ства:

;

;

Для доказательства справедливости любых из приведенных тождеств нужно составить таблицы истинности для булевых функций.

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

Формула φ(x₁,..., x_n) называется выполнимой (опровержимой), если существует такой набор значений переменных, при котором формула принимает значение 1 (соответственно 0).

Пример 1. Формула ху является одновременно выполнимой и опровержимой, поскольку 00 = 0, а 11 = 1.

Формула φ(x₁,..., x_n) называется тождественно истинной, общезначимой или тавтологией, если эта формула принимает значение 1 при всех наборах значений переменных, т. е. функция f является константой 1.

Пример 2. Формула является тождественно истинной, одновременно выполнимой01 = 1, 11 = 1.

Формула φ(x₁,..., x_n) называется тождественно ложной или противоречием, если эта формула принимает значение 0 при всех наборах значений переменных, т. е. функция f является константой 0.

Пример 3. Формула является тождественно опровержимой, поскольку00 = 0, а 01 = 0.

Если φ - тождественно истинная формула, то будем писать |= φ Пример.|= . В противном случае пишем |φ. Пример |.

Очевидным является следующее

Замечание

1. Формула φ тождественно ложна тогда и только тогда, когда неφ тождественно истинна (|=неφ );

2. Формула φ опровержима тогда и только тогда, когда она не является тождественно истинной (|φ);

3. Формула φ выполнима тогда и только тогда, когда она не является тождественно ложной.

Тождественно истинные (соответственно тождественно ложные) формулы образуют класс эквивалентности по отношению ~.

4. Если формула φ₁ тождественно истинна, φ₀ - тождественно ложна, то для любых формул φ и ψ справедливы следующие эквивалентности:

φφ₁ ~ φ; φφ₀ ~ φ₀;

φφ₁ ~ φ₁; φφ₀ ~ φ;

~ φ₁; ~ φ₁;

~ φ₀; ~ ; ~ φ.

Графический способ задания булевой функции

Единичный n-мерный куб функции w = f(x, y, z)

Задняя 001 011 Задняя 101 111

Грань передняя

000 001 100 110

Фактор-алгебра алгебры формул

Обозначим через Ф_n множество всех формул алгебры логики с переменными из множества {х₁, х₂, ... , х_n}.

На множестве Ф_n определены двухместные операции конъюнкции и дизъюнкции — :,:— и одноместная операция отрицания:.

Выделим на множестве Ф_n две константы и. Так получаетсяалгебра формул F_n = .

Отношение ~ эквивалентности формул является конгруэнцией на алгебре F_n, и поэтому можно задать фактор-алгебру F_n/~.

На фактор-множестве Ф_n/~ операции ,иопределяются следующим образом:

~(φ)~(ψ) = ~( φψ),

~(φ)~(ψ) = ~( φψ),

~(φ) = ~( φ),.

На множестве Ф_n/~ выделяются две константы: 0 = ~() и 1 = ~(). Полученная система является фактор-алгеброй F_n/~.

Теорема. Фактор-алгебра F_n/~ изоморфна алгебре булевых функций B_n

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

Искомый изоморфизм ξ: F_n/~ → B_n определяется по следующему правилу: классу эквивалентности ~(φ) сопоставляется функция f_φ, имеющая таблицу истинности произвольной формулы из множества ~(φ). Поскольку разным классам эквивалентности соответствуют различные таблицы истинности, отображение ξ инъективно, а так как для любой булевой функции f из В_п найдется формула , представляющая функциюf, то отображение ξ сюръективно. Сохранение операций , 0, 1 при отображении ξ проверяется непосредственно. ЧТД.

По теореме о функциональной полноте каждой функции , не являющейся константой0, соответствует некоторая СДНФ ψ, принадлежащая классу ~(φ) = ξ^-1(f) формул, представляющих функцию f. Возникает задача нахождения в классе ~(φ) дизъюнктивной нормальной формы, имеющей наиболее простое строение.

Контрольные вопросы

1. Что такое булева функции? Понятие «булева функция», булевы функции одной переменной. Булевы функции двух переменных.

2. Что называется высказыванием? Понятие «высказывание». Приведите примеры высказываний. Какие высказывания называются истинными, а какие ложными?

3. Что называется составным высказыванием?

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

5. Какие основные операции используются в теории высказываний? Простейшие связки. Назовите другие связки.

6. Что такое таблица истинности высказывания и как она строится?

7. Сформулируйте основные законы алгебры высказываний. Как их доказать?

8. Булевы функции: понятия формула, подформула, базис. Равносильные формулы. Принцип двойственности.

Лекция № 9

Так как здание всего мира совершенно и возведено премудрым Творцом, то в мире не происходит ничего, в чем не было бы виден смысл какого-нибудь максимума или минимума.

Эйлер