Тема 5. Математическая логика

План:

1. Высказывания
2. Логические операции  над высказываниями
3. Булевы функции
4. Необходимое и достаточное условия, понятие теоремы
5. Законы алгебры логики
6. Законы правильного мышления
7. Нормальные дизъюнктивные и конъюнктивные формы
8. Минимизация функций алгебры логики
9. Сумма по модулю два, операция двоичного сложения

10. Полнота множества функций

11.  Логические схемы.

12.  Контрольная работа.

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

Теоретические сведения

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

Логика – наука[1], изучающая методы доказательства и опровержений, то есть методы установления истинности или ложности одних высказываний (утверждений) на основе истинности или ложности других высказываний.

В этой главе будут рассмотрены  элементы математической логики. В ее основе лежит логика высказываний, в которой выска­зывание рассматривается как особое буквенное исчисление – алгебра логики.

Математическая логика изучает схемы (формы) истинных высказываний, имеющих наибольшую степень общно­сти, схемы математических доказательств и правила их вывода. Изучение исчисления высказываний как алгебраической системы составляет предмет алгебры логики, или булевой алгебры.

Математическая логика – современная форма логики, которая полностью опирается на формальные математические методы.

Сократу приписывают удивительные по глубине слова: “Я знаю только то, что я ничего не знаю, но другие не знают и этого”. Эти слова точно передают знания людей в области логики

1. Высказывания

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

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

Высказывание – суждение, утверждающее что-либо о чем-либо, если можно сказать, истинно оно или ложно в. данных условиях места и времени.

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

Характери­стика суждения по признаку истинности-ложности называется семантической.

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

Задание 5-1. Установите по определению высказывания,  предло­жения, которые  можно назвать высказываниями.

1. Умение грамотно использовать логические операции повы­шает эффективность программирования.

2.  История логики насчитывает около двух с половиной тыся­челетий.

3.  Знание математической логики необходимо любому специа­листу.

4.  Математическая логика – увлекательная наука.

5.  х>5

6 2·2=5

7. Он – программист.

8. На улице холодно.

Ответ и комментарии. Предложения I, 2, 3, 6 являются высказываниями, а 8 – нет. Предложения 4,5, 7 – не высказывания, но они ними становятся при конкретных заданных значениях. Например, вместо предложения “Он – программист”, запишем “Иванов программист”. Последнее суждение – высказывание.

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

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

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

Задание 5-2. Приведены сложные высказывания. Установите логические связки, с помощью которых образуются составные выказывания. Выделите из них простые высказывания.

1. Все программисты имеют высшее или сред­нее специальное образование.

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

3. Завтра я дойду гулять, если будет хорошая погода.

4. Число 55 больше или равно числа33

5. Дискретная математика включает раз­делы: элементы теории множеств”, элементы теории графов”, элементы классической и математической логики, элементы теории автоматов

Поскольку языком алгебры логики служат булевы функции[2], то естественно смысловым связкам поставить в соответствие опера­ции над булевыми переменными. Это:

1. Если простое высказывание является истинным, то ему соот­ветствует значение логической переменной 1.

2. Если простое вы­сказывание является ложным, то ему соответствует значение ло­гической переменной 0.

3. Если выполняется все (составное) вы­сказывание, то оно является  истинным и ему соответствует 1, если не выполняется, то высказывание -ложное и ему соответствует 0.

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

Для того чтобы определить, истинно или ложно некоторое сложное высказывание, используют таблицы истинности, в ко­торых латинскими буквами обозначаются сами высказывания, а цифрами 1 и 0 их семантическая характеристика – соответственно истина  или ложь.

Задание 5-3. Установите истинность высказываний.:

1. A: “В классе присутствуют 25 учащихся”

2. Q:  “p » 3,14″

3. M:  “p, s, v, x, y, z  – буквы греческого алфавита”.

4. D:  “1‰ – один промилле составляет тысячную долю числа”

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

1. отрицание  (инверсия)- не,
2. дизъюнкция  строгая – либо  и нестрогая – или,
3. конъюнкция  – и,
4. импликация – если… то,
5. эквиваленция  – тогда и только тогда.

2. Логические операции  над высказываниями

	Название операции	Определение  операции	Обозначение операции
1	Конъюнкция	A и B	A  Ù  B;   A  & B;   A  Ç  B;   A·B
2	Дизъюнкция	A или   B	A  Ú B;   A  È B;   A + B
3	Импликация	если A  то   B	A  →  B
4	Эквиваленция	A тогда и только тогда, когда   B	A ↔ B
5	Отрицание	не A;   не верно, что A	ù A;   Ā
6	Стрелка Пирса	не верно, что A или   B	A ¯  B,  ù (A  Ú B)
7	Штрих Шеффера	не верно, что A и  B	A ½  B,   ù (A  Ù B)
8	Запрет	не A и B	Ā · B

Физический смысл некоторые логических операций

Пусть d и h выключатели,

Обозначим их состояния на схеме символами:

1. Конъюнкция:

2. Дизъюнкция

3.Отрицание:          – элементы,  отрицающие друг друга

4.Стрелка Пирса (отрицание дизъюнкции)

5. Штрих Шеффера (отрицание конъюнкции)

6. Запрет

Определения логических операций.

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

Дизъюнкцией (нестрогой или соединительной) высказыва­ний А или В называется высказывание, которое истинно тогда и только тогда, когда истинно хотя бы одно из этих вы­сказываний.

Конъюнкцией высказываний А и В называется высказывание АВ, которое истинно тогда и только тогда, когда истинны оба высказывания.

Строгой дизъюнкцией высказываний А и В называется высказы­вание  А ≫ В, которое истинно тогда и только тогда, когда истин­но только одно из этих высказываний.

Импликацией высказываний А и В называется высказывание А → В, которое ложно тогда и только тогда, когда из истины сле­дует ложь.

Эквивалентен высказываний Аи В называется высказывание А <-> В, которое истинно тогда и только тогда, когда либо истин­ны, либо ложны одновременно оба высказывания.

Каждую логическую операцию можно иллюстрировать с помощью кругов Эйлера.  При этом можно усмотреть такие соответствия:

-         дизъюнкции -логическая сумма – объединение множеств,

-          конъюнкции – логическое произведение

-          пересе­чение – произведение множеств,

-         строгой дизъюнкции – сумма по модулю 2

-          прямая сумма- отрицанию

-          разность, имплика­ции – подмножество.

Высказывание на русском языке	Название операции	Таблица истинности	Круги Эйлера
Не А Неверно, что А А не имеет места	Отрицание, инверсия	А    А 0     1 1     0
А или В; Или А, или В, Или оба вместе	Нестрогая дизъюнк­ция (соеди­нительная)	А    В A∨B 0       0       0 0       1       1 1       0       1 1       1       1
1. Либо А, либо В; А или В, но не оба   вместе	Строгая дизъюнкция (разделитель­ная)	А    В     А ∨ В 0     0      0 0     1      1 1     0      1 1     1      0
1. Аи В; Как А, так и В; Не только А, но и S; 4. А вместе с Б; 5. А, несмотря на В; А, в то время как В	Конъюнкция	А    В    А В 0     0       0 0     1       0 1     0       0 1     1       1
1. Если А, то В; А, только если 5; 3. А достаточно для В; 4. В необхо­димо для А; 5. А вле­чет В’, 6. В тогда, ко­гда А; из А следу­ет В	Импликация, следование	А    В   А→ В 0    0      1 0     1     1 1     0     0 1     1     1
1. А эквивалентно В; 2. А тогда и только тогда, когда В; 3. А, если и только если В; А необхо­димо и достаточ­но для В	Тождествен­ность, равно­сильность, эквиваленция	А    В   А→В 0    0        1 0     1       0 1     0       0 I     1       1	Круги совпадают

Задание 5-4. Составьте сложные высказывания из простых высказывание с применением всех возможных связок.

1. Простые высказывания: “Максимов – хороший программист” (А) и “Он побеждает на олимпиадах” (В).

Решение.

-  Конъюнкция АВ. “Максимов – хороший программист и он побеждает на олимпиадах” или “Максимов – хороший програм­мист, он побеждает на олимпиадах”.

- Нестрогая дизъюнкция A v В: “Или Максимов хороший про­граммист, или побеждает на олимпиадах”.

Отрицание: – Строгая дизъюнкция А ^ В: “Либо Максимов хороший програм­мист, либо побеждает на олимпиадах”.

- Импликация А -> В: “Если Максимов хороший программист, то он побеждает на олимпиадах”; “Для того чтобы Максимов по­беждал на олимпиадах, достаточно, чтобы он был хорошим про­граммистом”.

- Эквиваленция А -о В: “Максимов хороший программист тогда и только тогда, когда он побеждает на олимпиадах”. “Максимов хо­роший программист только когда он побеждает на олимпиадах”.

2. Для высказывания “Х> 5″ (А) составить отрицания.

Решение.

-         неверно, что X > 5, “                      – X не более 5             -   X< 5 или Х=5

3. Составить отрицания. Прямая а, лежащая на плоскости, не пере­секает окружность.

Решение

- Не­верно, что прямая а, лежащая на плоскости, не пересекает окружность

- Прямая а, лежащая на плоскости, пересекает окружность.

- Прямая а, лежащая на плоскости, имеет с окружностью общие точки.

Добавление частицы не и слова неверно может не пре­вратить высказывание А в отрицательное А: “Максимов – хоро­ший программист” и “Неверно, что Максимов – хороший про­граммист”, так как речь может идти о разных Максимовых.

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

Формализацией высказываний называют операцию замены вы­сказывания естественного языка формулой математического язы­ка, включающего высказывательные переменные и символы тех логических операций, которые соответствуют структуре самого высказывания

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

Придав высказываниям вид исчислеия и, создав алгебру высказываний, можно развить аппарат на более понятном (например, числовом) множестве. За­тем, построив биекцию на семантическое множество {истина, ложь}, получается алгебра логики. Теперь надо выбрать числовое множество, где числовые символы будут соответствовать истине и лжи.

№	Две переменные
	X	Y
0	0	0
1	0	1
2	1	0
3	1	1

Таковым является множество {0, 1}.

Эти символы занимают мало места  и удобна техниче­ская их реализация: есть сигнал – (1), нет сигнала – (0).

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

№	Три переменные
	X	Y	Z
0	0	0	0
1	0	0	I
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7	1	1	1

-  для двух переменных от 0 до 3 – четыре значения

-  для трех переменных от 0 до 7 – восемь значений.

-  для четырех переменных от 0 до 15 -  шестнадцать значений.

Причем,  на нулевом месте –  все 0, на последнем  – все 1.

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

Например, задана функция, значение которой от наборов  4,6,7 равны 1.

Для упрощения формул, будем учитывать ряд правил.

1.Первой выполняется конъюнкция между элементарны­ми высказываниями и их отрицаниями;

2. Дизъюнкция выполняется раньше импликации и эквиваленции

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

Задание 5-5. Составить таблицы истинности высказываний.

1.                           2.

3.            4. F=(X   Y) ∩ (Z∩Y)

5.                    6.

Задание 5-6. Используя таблицу истинности установить эквивалентность функций в формулах.

1. A+B = (A+B) & (A+ ùB)                            3. (A+B & C)+A=A & B+(ùC+A)

2. (A+B) & C=A & C+B & C                        4.

3. Булевы функции.

Булевой функцией n пе­ременных называется отображение  f: :Вⁿ → В, заданное  множество В= {0, 1}..

Областью определения булевой функции являются кортежи дли­ной n, состоящие из символов 0 и 1. При этом каждому варианту кортежа должен быть поставлен в соответствие единственный эле­мент из В – значение булевой функции, например f (0, 1, 1, 0) = 0.

Поскольку в В всего два элемента, то снятие разделяющих запятых не нарушит однозначного восприятия кортежа, напри­мер /(0, 1, 1, 0) =/(0110) = 0.

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

Булева  функция n переменных может  иметь  m=2″ аргументов, соответствующих двоичным числам, имеющим n знаков  от   000…00 до 111..11

Количество различных булевых функций n переменных вычисляется  по формуле   или  более понятно k=2^m, где m=2ⁿ.

Пусть n=2, тогда m=2ⁿ=2²=4 – число аргументов и  k=2⁴=16– число булевых функций.

Для рассмотрения свойств булевых функций выполним геометрическую интерпретацию в виде n-мерного куба. M=2ⁿ – число вершин такого куба.

При n=3 получается общепринятый куб с m=8 вершинами – трехмерный куб.

При n=2 получим m=4 – квадрат или двумерный куб.

При n=1 получим m=2 – отрезок или одномерный куб

При т=0 получим m=1 – точка  или ноль мерный куб

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

Такой n-мерный куб бу­дет однозначно задавать любую булеву функцию /(x₁ х₂, …, х_n) с nпеременными.

Равенство функций.

Как для отображений вообще, для булевых функций справедливо определение равенства функций. С учетом области определения две булевы функ­ции f и g, зависящие от n переменных, называются равными (эк­вивалентными), если для любого xÎ Вn справедливо соотношение f(х) = g(x). Проверить эквивалентность двух функций можно с помощью таблиц истинности. Преобразование булевой функции применением заданных эквивалентностей (формул) дает но­вую функцию эквивалентную исходной.

Формулы.

Напоминание. Композицией функций f_{1 …}f_n на­зывается функция f полученная с помощью подстановок этих функций друг в друга и переименования переменных. Об этом было сказано в предыдущих разделах.

Форму­лой называется выражение, соответствующее композиции функций f_{1 …}f_n , описывающее ее.

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

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

Гово­рят, что формула представляет или реализует соответствующую логическую функцию.

Практически композицией двух булевых функ­ций f (от n переменных) и g (от т переменных) будет функция h(х). Причем,  для любого  x ÎBⁿ h(x) =g(f_}, …, f_m)(x) = g(f_}(x), …, f_m(x)).

В процессе формализации учитываются следующие правила.

1. Простому высказыванию соответствует элементарная формула.

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

~       выделить все элементарные высказывания и логические связ­ки, соответствующие структуре высказывания;

~       заменить их соответствующими символами;

~       расставить скобки в соответствии с логической структурой высказывания.

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

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

Булевы функции одной переменной.

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

F₁ =0 – тождественный ноль

F₂ =x – тождественная функция

F₃ = - отрицание (инверсия)

F₄ =1 – тождественная единица

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

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

Булевы функции двух переменных. При п = 2 существуют 16 булевых функций. Они представлены  в таблице.

x1	x2	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f15	f15	f16
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

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

1. Симметрические функции.

f₂ = (0001) – конъюнкция (объединять)

f₈ = (0111) – дизъюнкцияz (разделять).

fю= (1001) – эквиваленция (равно­значный).

f₇ = (0110) – сумма по модулю два.  (строгая дизъюнкция): Функция

f₉ = (1000) - стрелка Пирса или отрицанием дизъюнкции.

f₁₅ = (1110) – штрихом Шеффера. или  отрицанием конъюнкции.

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

Общее правило.

Любые две функции, распо­ложенные симметрично относительно центральной вертикальной оси таблицы значений, будут взаимно инвертированными

2. Импликации.

f₁₄ = (1101) – импликацияz, или следуемость (тесно связывать).

fз = (0010) и f₅ = (0100) – отрицание имп­ликаций f₁₄ и f₂ соответственно.

3. Функции, явно зависящие от одной переменной.

f₄ =  (0011), все значения которой совпадают со значениями первой переменной, обозначается f (х, у) ~ х. Аналогично f₆= (0101) = у.

fз = (1100) и f₁₁ – (1010) являются отрицаниями/, и f₆ соответственно.

Способы задания булевых функций.

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

Соглашения (требования) о написании формул.

Определены правила ком­пактной записи булевых функций и порядок их упрощения.

1. Внешние скобки не используются.
2. Действия в скобках выполняются в первую очередь.

3. Учитываются приоритеты логических операций в порядке воз­растания: отрицание, следствие, конъюнкция, дизъюнкция.

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

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

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

4. Необходимое и достаточное условия, понятие теоремы.

Все логические операции имеют широкое применение в обыч­ной речи. Но особенно важное значение в познании имеют опера­ции импликации и эквиваленции.

Примеры импликаций и эквиваленций.

1. Высказывание А: “Выполнил домашнее задание” и В: “Получил пятерку”

Импликация А -> В.  “Если выполнил домашнее задание, то получил пятерку”. Она истинности для этого высказывания примет вид

2. Высказывания:  А= “Через проводник пропустили ток”

В= “Длина проводника увеличилась”.

Импликация. “Если через проводник пропустили ток, то его длина увеличится”.

“Если ток пропущен, то  длина проводника не увеличилась”- ложная импликация

“Если и ток не пропустили, и длина не увеличилась” – вывод станет истинным.

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

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

Пусть из высказывания A следует высказывание B, тогда A – условие, B

Задание 5-7. Составить для истинной импликации  обратную импликацию и установить ее истинность.

1. Если через про­водник пропущен ток, то его длина увеличится.

Решение. Но про высказывание “Если длина проводника увеличилась, то через него пропустили ток” нельзя сказать, истинно оно или ложно, так как увеличение длины проводника не является причиной того, что через этот проводник стали пропускать ток.

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

Решение. Если получил пятерку, то выпол­нил домашнее задание – вообще говоря, неверно.

3. Сформулируйте признаки делимости чисел с применением необходимых и достаточных условий. Запишите обратные им высказывания и установите их истинность.

4. Приведите  импликации и запишите обратные им высказывания и установите их истинность.

Понятие теоремы

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

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

Для каждой теоремы можно сформулировать четыре теоремы

1.  Из А следует В  – прямая терема.

2.  Из В следует А  – обратная теорема.

3.  Из не А следует не В – противоположная теорема.

4.  Из не В следует не А – обратная противоположной теорема.

Задание 5-8. Выделите основные части теорем, сформулируйте остальные теоремы, установив их истинность. Сформулируйте теоремы с применением необходимых и достаточных условий.

1. Теорема Пифагора “В прямоугольном треугольни­ке квадрат гипотенузы равен сумме квадратов катетов”, надо выделить условие и заключение.

Решение. Новая формулировка этой теоремы согласно наложенным требованиям, имеет вид: “Если дан прямо­угольный треугольник, то квадрат гипотенузы равен сумме квад­ратов его катетов”. Первая честь формулировки – условие, вторая – заключение, то, что идет речь о геометрической фигуре – треугольнике – разъяснительная часть.

Сравним с привычной записью условия теоре­мы в геометрии.

Дано: Треугольник АВС – прямоугольный,  угол C = 90°, сторона с - гипотенуза, стороны а, b – катеты.

Доказать: с² = а^г + Ь².

2. Вертикальные углы равны.

Комментарии. Поэтому и говорят, что высказывание “Углы вертикальные” является достаточным для утверждения “Углы равны”. А равен­ство углов необходимо, чтобы утверждать, что речь идет о верти­кальных углах. Невыполнение необходимого условия (его ложность) влечет за собой невыполнение достаточного условия, например “Если углы не равны, то они (в принципе) не могут быть накрест лежащими”.

3. Четные числа делятся  на  2.

4. У квадрата диагонали равны.

Комментарии.

Для того чтобы диагонали четырехугольника были равны, до­статочно, чтобы четырехугольник был квадратом;

Равенство диагоналей четырехугольника – необходимое усло­вие для существования прямоугольника;

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

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

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

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

Эквиваленцию можно использовать в определении всех логи­ческих операций.

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

Таблица истинности для эквиваленции
А	В	А → В	В→А	(А → В) • (В → А)	А ↔ В
0	0	1	1	1	1
0	1	1	0	0	0
I	0	0	1	0	0
1	1	1	1	1	1

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

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

Слово – любой набор символов из алфавита. Формула – слово, но не всякое слово есть формула.

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

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

Рассмотрим их для операций дизъюнкции и конъюнкции, учи­тывая свойство двойственности. Двойственность операций заключается в том, что если в формуле, содержащей лишь опера­ции дизъюнкции, конъюнкции и отрицания, заменить операции л и v на v и л соответственно, а символы 1 на 0 и 0 на 1, то получатся новые равносильности.

Законы Де Моргана называют переносом отрицания через ло­гические связки,

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

5. Законы алгебры логики

Дизъюнкция	Законы	Конъюнкция
a v b = b v a	Переместительный закон	ab = ba
a v (b v с) = = (a v b) v с	Сочетательный закон	a(bc) = (ab)c
a(b v с) = ob v ас	Распределительный закон	a v (be) =  (a v b)(a v c)
a v a = a	Правила идемпотент­ности	a · a = a
ù (a v b) = ù а ·ù b	Законы Де Моргана	ù (ab) = ù a vù b
a v 0 = а	Правила операций с константами	a-0 = 0
a v 1 = 1		a · 1 = a
a v ab = a	Законы поглощения	a(a v b) = a
a vù (ab) = a v b		a(ù a v b) = ab
a v ù а = 1	Законы инверсии (отрицания)	a ·ù a = 0
ab v aù b = a	Законы склеивания	(a v b) · (a v ù b) = a

ùù а = а – снятие двойного отрицания;

а -> b = ay b - снятие импликации;

a~b = ab v a-_b – снятие эквиваленции;

а v b = ab v ab~ снятие строгой дизъюнкции.

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

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

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

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

С помощью таблицы истинности (или таблицы состояний) можно описать все возможные комбинации входных пере­менных, что имеет широкое практическое значение.

Такая табли­ца позволяет анализировать контактную технологическую струк­туру с помощью записи в систематизированном виде состояний ее выхода для всех возможных состояний входов. Математическая логика является тем прочным теоретическим фундаментом, на котором основаны многие технические, а У- истинно. Во всех остальных случаях она – ложна.

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

Формула А называется тождественно-истинной, или тавтоло­гией, если она принимает значение “истинно” при всех значениях переменных, входящих в нее. Иными словами, тавтологией явля­ется функция, где все переменные фиктивны и хотя бы при од­ном наборе значений аргументов ее значение равно 1.

Формула называется тождественно-ложной, если она прини­мает значение нуль при всех значениях переменной, входящих в нее.

6. Законы правильного мышления

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

Логические законы универсальны, едины для всех людей, объектив­ны, т. е. не зависят от наших знаний или желаний. Три первых логических закона были сформулированы Аристотелем в IV в. до н. э. в “Аналитике” и “Метафизике*. Четвертый закон был сформулирован Лейбницем в “Мо­надологии”.

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

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

Итак, законы мышления - это необходимая, существенная и устойчивая связь между мыслями. Они отражают в сознании лю­дей связь между предметами объективного мира, имеют общече­ловеческий характер и сформулированы на основании свойств мышления – определенности, непротиворечивости, обоснован­ности, четкости выбора. Законы правильного мышления, как наи­более общие, лежат в основе операций с понятиями, суждения­ми и умозаключениями, причем не только в общении между людь­ми, но и в основе работы ЭВМ.

1. Закон тождества

Задается формулой а~а (а есть а}.

В процессе рассуждений всякое понятие и суждение тождествен­но самому себе.

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

Правила соблюдения закона тождества.

1. Мысль или понятие не подменяется другой мыслью или понятием.

Особенно это часто проявляется в спорах, где нередки подмена тези­са и другие ошибки в доказательствах. (“Кто про Фому, а кто про Ер ему”.)

2. Недопустима замена слов омонимами (игра слов).

Примером такой игры слов может служить эпиграмма Николая Минского: “Переводи­мы все – прозаик и поэт. Лишь переводчики – им перевода нет”, а также знаменитая фраза “Ученик прослушал рассказ учителя”.

3. Нельзя путать формальное тождество с содержательным.

На этой ошибке основаны многие софизмы: “Сидящий встал. Кто встал, тот стоит. Значит, сидящий стоит”; “2 и 3 есть четное и нечетное. 2 и 3 есть 5. Значит, 5 есть четное и нечетное”.

4. Нельзя использовать неопределенные термины или некорректно их формулировать. Например, нечеткий вопрос спровоцировал не­адекватный ответ:

-  У вас затопили?

- Да, со всех сторон, даже сверху…

Тонко подметил такие логические ошибки Льюис Кэрролл в книге “Алиса в Стране чудес”: “Все понятно! – с торжеством ска­зал Шляпа. – Провести время? Ишь чего захотела! Время не про­ведешь! Да и не любит он этого! Ты бы лучше постаралась с ним подружиться – вот тогда бы твое дело было… в шляпе!”

Широко применяется закон тождества в точных науках, на­пример в математике, информатике и т.д. Рассмотрим несколько примеров его применения.

1. Замена различными буквами значения некоторой перемен­ной, например подстановка. Переменная заменяется на свое кон­кретное значение, выражение – на тождественное себе и т.д. При­мером может служить тождественность при использовании сим­волов отрицания <? и -л.

2.  Тождественные преобразования выражений: (а + Ь)² – а² + ab + + ba + b²;

cos2a. = cos²a-sm²a;

3. Тождественны свойства отношений эквивалентности,: рефлективности симметричности, транзитивности:

4. В теории алгоритмов и теории кодирования (см. гл. 6) равны числа в различных алфавитах: 2₁₀ = 10₂; 3₁₀ = 11₂; 4_Ю = 100₂ и т.д.

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

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

В процессе движения происходит изменение образа. Например, процесс старения человека (Иванова), изменение погодных усло­вий в данном городе (М), но при этом сам Иванов или город М остаются в нашем восприятии и в восприятии государства тем же человеком и тем же городом. У Иванова сохраняется номер паспор­та, а город М является определенным административным центром и получает столько-то полномочий и бюджетных денег.

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

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

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

У Аристотеля формулировка закона имела вид: “Невозможно что-либо одновременно утверждать и отрицать”.

Современная формулировка выглядит так: “Два противополож­ных или противоречащих суждения, взятых одновременно, не мо­гут быть истинными в одном и том же отношении, в одном и том же месте”. Например, известное выражение “Я – не я, и лошадь не моя”.

Смысл этого закона заключается в требовании не допускать противоречивых мыслей. Универсальность закона противоречия проявляется в работе с понятиями и суждениями (Л и А противо­речивые), а также с умозаключениями, которые должны быть непротиворечивы. На использовании этого закона основаны, на­пример, непосредственные умозаключения через превращение суждений. Порой закон противоречия называют законом не  про­тиворечия, отождествляя название закона с его действием (и при этом нарушают законы логики).

Правила соблюдения закона противоречия.

1. Нельзя допускать взаимоисключающие суждения в структуре од­ного предложения.

2. Необходимо давать истинные определения и оценки суждений.

3. Необходимо выявлять как явные, так и скрытые противоречия, но при этом различать реальные и мнимые противоречия.

2. Закон логического противоречия.

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

Например, не могут быть одновременно истинными или лож­ными общеутвердительное и общеотрицательное суждение об од­ном и том же: “Все люди применяют законы логики”, “Ни один человек не применяет законов логики” или общеутвердительные и общеотрицательное суждения: “Все студенты сдали экзамены за I семестр”, “Некоторые студенты сдали экза­мены за I семестр”.

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

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

Потребность решить уравнение типа 15 + х= 9 привела к от­крытию отрицательных чисел (х = -6). Стремление решить урав­нение вида 5х = 9 привело к открытию обыкновенных дробей (х = 9/5). Попытки решить некоторые квадратные уравнения вида х² = 2 привели к открытию иррациональных чисел. По­требность в решении уравнений вида х² = ~1 привела к открытию комплексных чисел

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

Особое значение имеет закон противоречия в ходе проведения доказательств. С этим же связан и четвертый закон правильного мышления. Он лежит в основе требований, накладываемых на до­казательства. Непротиворечивыми должны быть как используемые в доказательствах посылки (тезисы и аргументы), так и выводы этой теории.

В математике закон противоречия используется и при доказа­тельстве методом от противного.

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

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

Нельзя мириться с логическими противоречиями в обыденной жизни людей. Однако иногда юристы употребляют фразу “Отсут­ствие следа на месте преступления – тоже след”. Имеется в виду след опытного преступника, умеющего не оставлять следов.

Закон противоречия дополняет закон тождества. Это как бы крайние проявления различия вещей, их не тождественности. На­пример, день и ночь, зима и лето, живой и мертвый, горячий и холодный и т.д.

С помощью приема синтеза двух противоречивых понятий авто­ры – художники, писатели – могут придумать броское, привлека­ющее внимание и в то же время обнажающее проблемы название произведения: “Яблоки на снегу”, “Живой труп”, “Горячий снег”.

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

3. Закон исключенного третьего: “Из двух противоречивых суждений одно истинно, другое ложно, третьего не дано”

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

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

Правила соблюдения закона исключенного третьего.

1. Существуют две альтернативы А и А, между которыми надо сделать выбор.

2. Третьей альтернативы, т.е. некоторого суждения В = А = А, несуществует. .

3.  Между альтернативами установлено отношение противоречия – I одна является отрицанием другой.

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

Он же лежит в основе дихотомического деления, в котором также существуют две взаимоисключающие друг друга альтерна­тивы А и А. На законе исключенного третьего основано кодирова­ние информации для ЭВМ, а также вся математическая логика.

В природе и обществе существуют так называе­мые случайные явления: результаты голосования на выборах, стихийные бедствия, результаты экспери­ментов, поиска, в которых недостаточно двумерного Аристотелева языка оценок явлений. Приходится искать третью характеристику. Например, противопо­ложные умозаключения: индукция (от частного к обще­му) и дедукция (от общего к частному) не исключают и третьего вида – аналогии (от частного к частному). Та же лампочка, о кото­рой нам хочется думать, что она имеет два режима: горения горит, имеет переходное время. Просто это время у лампочки – 0,1с, а у электроплитки это время 5 мин, что уже сравнимо со временем ее эксплуатации, например кипячением воды.

Из этого закона можно сделать несколько выводов.

1. Не использовать закон исключенного третьего при оценке прогно­за, связанного с природными явлениями. Надо анализировать пред­метную область применения этого закона.

2. При решении некоторой проблемы в условии неопределенности надо выявить все альтернативные варианты с помощью здравого смысла, логики, закона исключенного третьего (четвертого и т.д.) и ком­бинаторики.

3. Оценить вероятность осуществления каждой альтернативы и ее последствий, опираясь на здравый смысл, интуицию, логику и мате­матику.

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

Приведем некоторые требования, которые накладывает на наши мысли закон исключенного третьего.

1. При голосовании либо “за”, либо “против” избегать варианта “воздержался”.
2. При подсчете голосов, если возникает паритет мнений, необ­ходимы повторные выборы и повторное голосование.
3. В ходе судебного расследования подозреваемый либо виновен, либо не виновен, но если вина на данный момент не доказана и есть сомнения, то дело отдается на доследование.
4. В медицинской практике пациент либо болен, либо не болен (здоров), но если диагноз не установлен, а симптомы болезни выявлены, то врач отправляет пациента на дообследование.
5. Во время учебы в учебном заведении учащийся либо знает кон­кретную тему, либо не знает. Если преподавателю в ходе ответа не удалось определить факт наличия знаний, или не удалось четко определиться с оценкой, то он задает дополнительные вопросы.
6. При отстаивании позиций в споре необходимо определить ин­теллектуальные границы, в которых осуществляется осознанный поиск истинного вывода.

4. Закон достаточного основания. “Всякая истинная мысль должна быть достаточно обоснована”

Этого закона  в логике Аристотеля не было, его сформулировал Лейбниц.

Ни одно суждение не может считаться истинным без достаточного на то основания.

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

1. В доказательствах можно использовать только истинные или обоснованные суждения.

2. Обоснования суждений могут быть логического и фактического характера.

Аргументами в обосновании могут служить:

- истинные суждения, аксиомы, нормы морали;

- фактический материал;

- законы науки, законы общества;

- теоремы.

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

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

Закон достаточного основания – логический, но он имеет прямое отношение к общефилософскому закону о причинно-след­ственных связях. В природе, обществе и любой науке, как в отра­жении законов природы и общества, все взаимосвязано. Любое событие, явление, суждение имеет свои причины и порождает следствия, – это объективные законы действительности. В XVIII в. М.В.Ломоносов в работе “Элементы математической химии” ис­пользовал аксиому: “Ничто не происходит без достаточного ос­нования”.

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

Но из-за двусмысленности толкования слова “следовательно” философское и житейское применение этого термина не всегда совпадает.

Классический пример: в природе “Пошел дождь, и (по­этому) крыша стала мокрой

В жизни, посмотрев в окно, мы сделали вывод: “Крыша стала мокрой, значит, пошел дождь”,

Чтобы избежать ошибок в заключениях, нужно придерживать­ся простых правил.

1. Вывод, основанный на ложных посылках, – ложен, точнее, не определен и не может служить дальнейшим аргументом.

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

Так, не является достоверным вывод “Студент получил на эк­замене двойку, значит, не выучил заданные вопросы”. На самом деле студент не выучил вопросы и поэтому на экзамене получил двойку. А первое утверждение неправильно, так как он мог, на­пример, выучить билеты, но нарушить дисциплину, передавая кому-то шпаргалки.

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

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

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

Доказательные рассужде­ния характеризуют научный стиль мышления.

В структуру доказательства входят следующие понятия.

Тезис - суждение, истинность которого надо доказать.

Аргументы основания - истинные суждения, которые исполь­зуются при доказательстве тезиса.

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

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

Сформулируем требования к видам аргументов.

Доказательства (рассуждения) моно классифицировать следующим образом

1. Прогрессивные – от оснований к следствию
2. Дедуктивные доказательства – от общего положения к тезису как следствию
3. 3. Доказательства полезности - от доказываемого положения к фактам, подтверждающим тезис
4. Индуктивные доказательства – от тезиса к основанию. От фактов как следствий к тезису

Определения. Не следует давать определения очевидным поня­тиям. Существуют неопределяемые понятия, например, в геомет­рии за неопределяемые понятия можно принять точку, простран­ство, в математике – множество, элемент, соответствие, в жиз­ни – любовь и т.д.

Не следует считать неопределяемыми те понятия, которым можно дать определения через неопределяемые и уже введенные понятия. Например, в математике: “Параллельными называются прямые, лежащие в одной плоскости и не имеющие общих точек”. Сравните с ошибочным определением, в котором используется

не определенный ранее термин “пересекающиеся”: “Параллель­ными называются прямые, лежащие в одной плоскости и не пере­секающиеся между собой”.

Аксиомы. Аксиома – это суждение, которое в рамках некото­рой науки или теории принимается истинным без доказательств.

Число аксиом должно быть необходимо и достаточно для вы­страивания рассуждений.

Одна аксиома не должна зависеть от всех других.

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

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

Примером полной теории может служить исчисление выска­зываний (см. подразд. 5.2). Неполными теориями являются ариф­метика и теория множеств.

Факты. В различных науках, в юриспруденции и т.д. фактиче­ский материал подтверждает или опровергает тезис. Для опровер­жения тезиса достаточно иметь один противоречащий ему факт. Например, формула простых чисел п - х² + х + 41 неверна при х= 41. О факте можно говорить лишь в прошедшем времени: он свершился, и есть достаточное количество надежных свидетелей, могущих это подтвердить. Вопрос заключается в том, какого сви­детеля считать надежным. Пусть, например, над средневековым Базелем пролетает самолет. Принципиальная возможность суще­ствования самолетов, разумеется не в средние века, доказана дей­ствительностью. Тогда весь город, скажем, десять тысяч человек, большая часть из которых находилась в здравом уме, скажут, что они были свидетелями божественного вмешательства: пролета не­чистой силы или, наоборот, ангел а-хранителя. Так же и в физике, где нет оснований считать людей глупыми, любой эксперимент не является таковым, пока не будет получена удовлетворительная трактовка его результатов в рамках существующих теорий. Если ее нет, то появляются новые теории, способные этот эксперимент объяснить. Так, ньютонова механика могла объяснить все явле­ния, пока не стали изучать электромагнитные явления.

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

Критика или опровержение - логическая операция установле­ния ложности или необоснованности тезиса. Ложность тезиса до­казывается с помощью аргументов опровержения. Опровержение должно показать неправильно построенное доказательство или ложность либо недоказуемость выдвинутого тезиса.

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

Логика вопросов и ответов

Велика роль вопроса в процессе познания истины, ведь путь от незнания к знанию идет через постановку вопросов и поиска от­ветов на них.

Этот процесс состоит из трех этапов: постановки вопроса, по­иска новой информации, конструирования ответа.

Грамматической формой вопроса является вопросительное пред­ложение.

Вопрос - это выраженная в вопросительном предложении мысль, направленная на уточнение или дополнение знаний.

Характерные особенности вопросов состоят в том, что, во-пер­вых, нет семантической характеристики (нет значений истины и ложности), во-вторых, опора делается на начальную исходную ин­формацию (предпосылка вопроса).

В зависимости от содержания предпосылки, ее истинности и непротиворечивости вопросы можно классифицировать на кор­ректные, некорректные и риторические.

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

С появлением компьютеров традиционная тема классической логики, логика вопросов и ответов, приобрела новое значение. Проблема “обучения” машины правилам общения с человеком стоит не только перед создателями ЭВМ. Ведь обучить машину ведению диалога оказалось легче, чем научить этому всех пользо­вателей ЭВМ. А грамотное ведение диалога становится необхо­димым для того, чтобы машина и человек говорили на одном, причем правильном, логически выверенном языке. Современный синтетический подход к диалогу с ЭВМ заключается в макси­мальном приближении этого диалога к естественно-речевому об­щению, что увеличивает эффективность восприятия информа­ции в системе человек-машина. Рассмотрим возможные вариан­ты такого диалога.

ЭВМ самостоятельно генерирует диалог согласно алгоритмам, заложенным разработчиками на основе строгих законов логики, т.е. самостоятельно моделирует ответы на реакцию партнера (че­ловека).

Вполне определенная модель беседы программируется заранее, а ЭВМ ведет диалог согласно этой программе.

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

Рассмотрим виды и познавательные функции вопросов (табл. 4.18).

Правила постановки простых и сложных вопросов.

Корректность постановки вопроса. В обычной речи недопусти­мы провокационные, риторические, некорректные вопросы.

Альтернативность ответов на уточняющие вопросы должна быть предусмотрена в самом вопросе.

Перечисление всех альтернатив сложных дизъюнктивных вопросов.

Краткость, ясность и простота формулировок.

Велика роль вопросов и ответов в процессе познания. Не менее важна точность формулировок вопросов и ответов при работе с компьютером.

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

В настоящее время логическая теория вопросов и ответов ин­тенсивно развивается именно в связи с применением ЭВМ. Так, современная компьютерная программа “Персональный доктор” основана на постановке диагноза “врачом-компьютером”, кото­рый следует после диалога ЭВМ с больным. Разработана специ­альная программа, предусматривающая возможные виды заболе­ваний с учетом реальных симптомов пациентов. Диалог ЭВМ с больным человеком заканчивается тем, что компьютер выдает конкретный диагноз и рекомендации по лечению. Конечно, он не может лечить или оперировать больного, но он помогает врачу определиться с выбором направления лечения. Причем скорость реакции “врача-компьютера” и энциклопедические знания, зало­женные в него человеком, делают его достойным помощником врача-человека. Но для работы с ним необходимо уметь правиль­но задавать вопросы и находить адекватную форму ответа.

7. Нормальные дизъюнктивные и конъюнктивные формы

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

Разложение функций по переменным. Нормальные формы

Рассмотрим булевы функции, представленные в виде суперпо­зиции элементарных функций И, ИЛИ, НЕ. Используя законы алгебры логики, можно заменить громоздкие булевы функции им равносильными, но более простыми. Такой процесс называется минимизацией булевых функций. Его проводят для упрощения слож­ных логических выражений в программах, а также для того, что­бы построенные на их основе функциональные схемы не содер­жали лишних элементов.

Минимизировать булевы функции надо, приводя их к так на­зываемой нормальной форме.

Существуют две разновидности нормальных форм – дизъюн­ктивные (ДНФ) и конъюнктивные (КНФ).

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

Например: или

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

Например:  

Нормальной дизъюнктивной формой называется   дизъюнкция конечного числа элементарных конъюнкций. Сокращенно обозначаются ДНФ

Нормальной конъюнктивной формой называется   конъюнкция конечного числа элементарных. дизъюнкций.  Сокращенно обозначаются КНФ

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

Предположим, что форма состоит из трех переменных и является ДНФ, содержащая две конъюнкции:

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

Аналогично можно сказать и про совершенную конъюнкцию, заменив в приведенном рассуждении конъюнкцию на дизъюнкцию и наоборот.

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

Из всех различных ДНФ функции F₁(x₁ ;x₂ ;x₃) особо выделяет­ся последнее логическое выражение, которое является совершен­ной ДНФ, сокращенно СДНФ. На СДНФ накладываются следу­ющие требования:

1. Формула не является тождественно-ложной;
2. Формула приведена к одному из видов ДНФ;
3. Из формулы удалены элементарные конъюнкции, включа­ющие одновременно переменную и ее отрицание, согласно зако­ну инверсии;
4. Из формулы удалены одинаковые элементарные конъюнкции, кроме одной, согласно правилу идемпотентности;
5. Каждая элементарная конъюнкция в ДНФ включает все логи­ческие переменные, входящие в эту формулу.

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

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

1. Формула не является тождественно-ложной;
2. Формула приведена к одному из видов КНФ;
3. Из формулы удалены одинаковые элементарные дизъюнкции, кроме одной;
4. Каждая элементарная дизъюнкция в КНФ включает все логи­ческие переменные, входящие в эту формулу.

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

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

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

№	x1	x2	x3	F
0	0	0	0	0
1	0	0	1	1
2	0	1	0	0
3	0	1	1	1
4	1	0	0	1
5	1	0	1	0
6	1	1	0	1
7	1	1	1	0

Запишем таблицу истинности для функции F(x_1, x₂, x₃). Слева от нее приведены номера наборов (строк), которые в последующих заданиях будем опускать.

В числовой форме эту функцию можно представить в виде:

f(x_{1 ,} x₂ , x₃)=1 для наборов 1,3,4,6 и f(x_{1 ,} x₂ , x₃)=0 для наборов 0,2,5,7. Часто такие наборы связывают их с  дизъюнктивными и конъюнктивными формами.

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

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

∨∨ x_{1 ;} x₂ ∨x₃ - примеры дизъюнктивных термов

Конъюнктивным  термом (мин термом) называется  терм, связывающий переменные в прямой или инверсной форме знаком конъюнкции.

∧∧ ∧x₁ ;      x₂ ∧ x₃∧ - примеры конъюнктивных  термов

Рассмотрим подробнее запись “f(x_{1 ,} x₂ , x₃)=1 для наборов 1,3,4,6″  и свяжем ее с дизъюнкцией конъюнктивных термов.

Вначале установим, что:

- набор 1 (0,0,1) соответствует  переменным (,, x₃)

- набор 3 (0,1,1) соответствует переменным (, x₂ , x₃)

- набор 4 (1,0,0) соответствует переменным (x_1, )

- набор 6 (1,0,0) соответствует переменным (x_{1 ,} x₂ , x₃)

Теперь первоначальную функцию можно представить в следующем виде дизъюнкции термов:

f(x_{1 ,} x₂ ,x₃) = ( x₃)È (x₂ x₃) È(x₁ )È (x₁ )È (x_1, x₂ x₃)  – получили СДНФ..

Замечание.

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

2. Выше приведенная запись  ”(x₁ x₂ x₃)=1 для наборов 1,3,4,6 ”

изначально можно задать следующим способом:  “f(x₁ x₂ x₃)= ÈF(1,3,4,6)”, которая означает, что задана дизъюнкция наборов, значения от которых равно 1.

3. Аналогично можно рассмотреть запись f(x₁ x₂ x₃)=0 для наборов 0,2,5,7 и связать ее  с конъюнкцией и получить СКНФ. Тогда запись “f(x₁ x₂ x₃)=0 для наборов 0,2,5,7″ может быть представленной в виде: “f(x_{1 ,} x₂ ,x₃) =&Ф(0,2,5,7)”

Если брать с инверсиями те переменные, которым соответствует число 1, а без инверсии – которым соответствует число 0, то не трудно установить, что рассматриваемая в качестве примера функция f(x_{1 ,} x₂ ,x₃) будет представлена в виде СКНФ следующим образом:

f(x_{1 ,} x₂ ,x₃) =( x_{1 ,} x₂ , x₃) &(x_{1 ,} , x₃ ) & (∨x₂∨)& ( ∨∨)

Алгоритмы составления ДНСФ и КНСФ по таблице истинности

Алгоритм составления ДНСФ по таблице истинности:

1. Дана таблица истинности.

2. Выделить все единичные значения функции.

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

3. Все минтермы соединить знаком дизъюнкции.

Алгоритм составления КНСФ по таблице истинности:

1. Дана таблица истинности.

2. Выделить все нулевые значения функции.

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

3. Все минтермы соединить знаком дизъюнкции.

Задание 5-9.

№	x1	x2	x3	f	Мин термы
0	0	0	0	1
1	0	0	1	1	x3
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1	1	x1 x3
6	1	1	0
7	1	1	1	1	x1 ,x2 x3

1. Функция некоторая функция f(x_{1 ,} x₂ ,x₃) трех переменных задана таблицей истинности, принимающей значения 1 на наборах 0,1,5,7. Определить ДСНФ

Решение. Составим таблицу истинности и введем в нее графу “Мин терм”

f _ДСНФ (x_{1 ,} x₂ ,x₃) =

=()∨( x₃)∨( x₁ x₃)∨( x_{1 ,}x₂ x₃)

№	x1	x2	x3	f	Макс термы
0	0	0	0
1	0	0	1
2	0	1	0	0	x1 x3
3	0	1	1	0	x1
4	1	0	0	0	,x2 x3
5	1	0	1
6	1	1	0	0	x3
7	1	1	1

2. Функция некоторая функция f(x_{1 ,} x₂ ,x₃) трех переменных задана таблицей истинности, принимающей значения 0 на наборах2,3,4,6. Определить КСНФ

f(x_1,x₂,x₃)=

=(x₁∨∨x₃)(x₁∨∨)(∨x₂∨x₃)( ∨∨x₃)

Практическим построением СДНФ показано, что любая буле­ва функция по таблице истинности разлагается в совершенную нормальную форму, т.е. в компози­цию отрицания, конъюнкции и дизъюнкции..

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

8. Минимизация функций алгебры логики

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

Как правило, такие функции могут упрощаться или, как говорят, минимизироваться. В результате получаются  минимизированные (сокращенные) формы. Из ДСНФ – минимизированная ДНФ или МДНФ,  из КСНФ – минимизированная КНФ или МКНФ.

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

Минимизация может иметь два направления: уменьшение ранга каждого терма  и (или) уменьшение числа символов в записи всей функции.

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

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

Непосредственное преобразование логических функций.

Алгоритм действий:

1. Строится таблица истинности заданной функции

2. Составляются мин термы.

3. Записывается ДНСФ логических функций.

4. Используя законы алгебры логики, упрощается ДНСФ

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

Напоминание: x_{1 ,}x₂ ∨x₁= x₁ и  (x₁ ∨x₂) (x₁∨)=x₁ –  операции склеивания.

Задание 5-10.

1. Задана функция, принимающая значения 1 в наборах: 0,1,2,3. Записать МДНФ

№	x1	x2	x3	f	Мин термы
0	0	0	0	1
1	0	0	1	1	x3
2	0	1	0	1	x2
3	0	1	1	1	x2 x3
4	1	0	0	0
5	1	0	1	0
6	1	1	0	0
7	1	1	1	0

Комментарии. Вначале записывается таблица истинности, в которой  наборам  0,1,2,3 соответствует число 1. Затем составляются мин термы. Долее записывается функция, состоящая из полученных мин термов

f (x_{1 ,} x₂ ,x₃)=∨x₃∨ x₂∨ x₂ x₃

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

f (x_{1 ,} x₂ ,x₃)= (∨x₃) ∨ x₂(∨x₃)=

= ∨ x₂=( ∨ x₂)=

Ответ: f (x_{1 ,} x₂ ,x₃)=  - МДНФ

2. Задана функция, принимающая значения 1 в наборах: 0, 2,3, 7.  Записать МДНФ

Метод Квайна

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

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

Алгоритм метода Квайна.

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

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

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

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

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

6. Результат записывается в виде функции.

Таблица 1
№	x1	x2	x3	f	Мин термы
0	0	0	0	0
1	0	0	1	0
2	0	1	0	1	x2
3	0	1	1	1	x2 x3
4	1	0	0	1	x1
5	1	0	1	1	x1 x3
6	1	1	0	0
7	1	1	1	1	x1,x2 x3

Задание 5-11.

1. Используя   метод   Квайна,   найти   МДНФ   для функции f (x_{1 ,} x₂ ,x₃), принимающей значение 1 на наборах: 2,3,4,5,7.

Комментарии.

1. Составляется таблица 1  истинности, по которой  и записываются все минтермы.

Таблица 2
Термы 3 ранга	Термы 2 ранга
x2*	x2
x2 x3 *	x1
x1*
x1 x3*
x1,x2 x3

2. Составляется таблица 2.

Склеиваются импликанты последовательно: 1-1,1-3,1-4,1-5. Возможным оказалось  импликат 1-3, около них поставим метку, получилась импликанта второго рангаx₂, которая записывается во вторую колонку таблицы 2.. Далее склеиваются 2-3,2-4,2-5. Склеивание 2-4 получает x₁, около них поставим метку.  Остальные склеивания 3-4, 3-5, 4-5 без результата.

Итак, получили три импликаты: (x_1,x₂ x₃),  ( x₂ ),  (x₁).

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

Первичные импликаты	Исходные минтермы
	x2	x1	x2 x3	x1 x3	x1,x2 x3
x2	*		*
x1		*		*
x1,x2 x3					*

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

Ответ. f (x_{1 ,} x₂ ,x₃)= x₂ ∨ x_1,x₂ x₃∨ x₁ – МДНФ.

2. Используя   метод   Квайна,   найти   МДНФ   функции f(x1,x2,x3,x4), принимающей значение 1 на наборах: 3,4,5,7,9,11,12,13.

Комментарии. Составляемые таблицы будут иметь следующий вид.

Ответ. f (x_{1 ,} x₂ ,x₃)= x₂ ∨  x₃ x₄∨ x₁ x₄ – МДНФ.

Метод Квайна — Мак – Класки

Недостаток  метода  Квайна – необходимость  полного  попарного сравнения всех минтермов на этапе нахождения первичных импликант. Идея модификации метода Квайна:

1.   Каждая конъюнкция в ДСНФ представляется своим двоичным набором.

2.   Вся совокупность номеров наборов разбивается на группы в зависимости   от числа единиц, имеющихся в номерах наборов (0-группа, 1-группа, 2-фуппа и.т.д.).

3. Сравниваются две группы, отличающиеся на одну единицу.

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

5.   В  процессе  преобразования   возникают  новые  сочетания  (п-группы).

6.   Процесс  преобразования  длится до  тех  пор,  пока  возможна операция склеивания.

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

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

Задание 5-12.

1. Используя метод Квайна – Мак — Класки найти МДНФ.

Функции f(x_1,x₂,x₃х₄), принимающей значение 1 на наборах:  0,1,2,3,4,5,6,7,8,9,11,15.

Решение.

Х1	Х2	Х3	X4	F
0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	1
0	1	0	0	1
0	1	0	1	1
0	1	1	0	1
0	1	1	1	1
1	0	0	0	1
1	0	0	1	1
1	0	1	0	0
1	0	1	1	1
1 .	1	0	0	0
1	1	0	1	0
1	1	1	0	\
1	1	1	1	1

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

2. Запишем n- группы:

0- группа: 0000

1- группа: 0001, 0010, 0100.1000

2- группа: 0011, 0101, 0110,1001

3-группа: 0111,1011

4- группа: 1111

3. Сравним  группы  с  номерами  i  и  i+1,  в  результате чего получим :

О- группа: 000-, 00-0, 0-00, -000

1-группа: 00-1, 0-01, -001, 001-, 0-10, ОЮ-,01-0, 100-

2- группа: 0-11, -011, 01 -1, 011 -, 10-1

3-группа:-111,1-11

4. Сравним (при этом прочерки должны быть на одинаковых позициях):

0- группа: 00-, 0-0-, -00-

1- группа: 0-1, -0-1, 0-1-, 01- -

2- группа: – -11

5 Сравним:

О- группа: 0—

6. Составим таблицу и найдем покрытие:

0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1011	1111
*	*	*	*	*	*	*	*	*	*	*	*	0-

	1000	1001	1011	1111
-00-	*	*
-0-1		*	*
-111			*	*

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

Ответ. f(x_1,x₂,x₃х₄)= ∨ x₂ x₃ х₄∨

Метод диаграмм Вейча (карт Карно)

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

Карты Карно являются одним из наиболее удобных способов минимизации. Они впервые появились в одной из статей Мориса Карно в 1953 г.

Карты Карно – специальные таблицы, дающие возможность упростить процесс поиска минимальной формы булева выраже­ния с помощью графического представления для п<6. Они имеют вид прямоугольника, разделенного на 2ⁿ клеток, в каждой из ко­торых – двоичный n-мерный набор значений функции f из таб­лицы истинности.

Для n= 2 карта Карно имеет вид таблицы, состоящей из 2² = 4 клеток, n=3, 2³=8 клеток, n=4, 2⁴=16.

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

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

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

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

Полная форма записи   карт Карно

n=4
	x1	x1
x2	110012	111014	01106	01004
	110113	111115	01117	01015	х4
	10019	101111	00113	00011	х4
	10008	101010	00102	00000
		x3	x3

n=3
	x1	x1
x2	1106	1117	0113	0102
	1004	1015	0011	0000
		x3	x3

n=2
	x1
x2	113	011
	102	000

Краткая форма записи   карт Карно

n=4	x1 x3
x3 х4	0000	0100	1000	1100
	0001	0101	1001	1101
	0010	0110	1010	1110
	0011	0111	1011	1111

n=2	х1
х2	00	10
	01	11

n=3	x2x3
x1	000	001	011	010
	100	101	111	110

В краткой форме  названия строк и столбцов не указаны,  но они подразумеваются.

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

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

Алгоритм  для карт Карно:

1.  Привести булеву функцию к ДНФ.

2.  Нанести единицы на карту Карно.  (Правила определения клеток для 1, рассматриваются при выполнении практических заданий, которые рассмотрены  ниже, сразу после этого алгоритма)

3.  Объединить соседние единицы контурами, охватывающими 2^т клеток, где т - 0, 1, 2, 3, При этом может оказаться, что еди­ница попадает одновременно в два контура. Если контур охваты­вает более одной пары единиц одновременно, то предпочтитель­нее его не дробить на пары, а рассматривать как целый единый контур, например квадрат.

4.  Провести упрощения, т.е. исключить члены, дополняющие друг друга до 1  внутри контура (например А и Ā),  следя за тем, чтобы переменные внутри контура были связаны операцией конъюнкции. Оставить отдельно по столбцам и по строкам общие (повторяющиеся) переменные – из них формируется оттает.

5.  Объединить оставшиеся члены (по одному в каждом конту­ре) дизъюнкцией.

6. Записать полученное упрощенное булево выражение.

Задание 5-13. Применение карт Карно к минимизации функций.

1. Минимизировать функцию  f(ABC) = Ā B∨Ā BC ∨AB∨ ABC.

Таблица истинности
№	A	B	C	f
0	0	0	0	0
1	0	0	1	0
2	0	1	0	1
3	0	1	1	1
4	1	0	0	0
5	1	0	1	0
6	1	1	0	1
7	1	1	1	1

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

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

0 – набор. f(000)=0, потому, что А=0, В=0, С=0 и хотя бы одно из них входят в каждую конъюнкцию формулы и поэтому каждая из них равна  0.

2- набор. f(010)=1, в виду того, что А=0, В=1, С=0 и хотя бы одно из них входят в каждую конъюнкцию формулы, причем  (Ā B) – 1,  (Ā BC) – 0,  (AB) - 0,  (ABC)  – 0.

7-набор. f(111)=1, в виду того, что А=1, В=1, С=1, причем хотя бы одно из них входят в каждую конъюнкцию формулы, причем  (Ā B) – 0,  (Ā BC) – 0,  (AB) - 0,  (ABC)  – 1.

Аналогично устанавливаются значения f для остальных   наборов.

Карта к № 5-13(1)
№1	Ā	ĀB	AB	A
С		1	1
		1	1

2. Составим карту Карно и расставим в ней 1, согласно таблице истинности. Обведем контурами соседние клетки, содержащие 1.

Комментарии.

Такое действие соответствует заключению в скобки слагаемых

Ā B ∨Ā BC и AB ∨ ABC

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

В данном примере этому шагу соответствуют конъюнкции

Ā В( ∨ С) и AB( ∨ С).

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

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

3. Полученный результат: f(A, В, С) = Ā В v AB = В (Ā v A)=В

Замечание.

№1	Ā	ĀB	AB	A
С		1	1
		1	1

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

Ответ: f(A, В, С) = В

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

Можно выполнить синтаксический способ минимизации

f(АВС) = (ABC v ABC) v ABC v ABC = AB v AB = B(AvA) = B.

2. Минимизировать функцию 

f (ABCD) = A v BD v D v CD v  BCD v AD

Комментарии.

Установим наборы, значения от которых равны 1 и занесем единицы в соответствующие клетки карты Карно  и объединим их двумя контурами.  Это можно сделать без таблицы истинности следующим образом. В виду того, что функция f есть ДНФ, то все ее конъюнкции соответствуют 1. В данной функции  их 6, значит клеток с 1 – тоже 6.

№2		D	CD	C
		1	1
B		1	1
AB
A	1	1

Строчкам даем названия, совпадающими с двумя  первыми символам каждой конъюнкции, устанавливаем их последовательность, например от инверсий до “нормальных” переменных. В данной задаче это ,  B, AB – этого сочетания нет в формах, которое введено для “порядка”, A.

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

На пересечение строк и столбцов, из имен которых составлена соответствующая конъюнкция, ставится 1. Например, первая в формуле конъюнкция имеет вид  A, значит на пересечении строки A – первая часть конъюнкции  и столбца  - вторая часть конъюнкции, ставится число 1. Для второй конъюнкции BD число 1 ставим на пересечении  строки B и столбца D. Идя последовательно по формуле заполоним 6 к леток таблицу по числу всех конъюнкций в формуле. Остальные клетки таблицы будут соответствовать  числу 0, т.к. для них в формуле нет конъюнкций.

2. В контуре – квадрате, общей переменной по строчкам является , а по столбикам – D. Результат по этому контуру равен  (D)

3. Во втором контуре общие переменные по строчке – A, по столбикам – . Результат по этому контуру равен (A)

Ответ. D∨A

3. Минимизировать функцию

f (ABCD) = AB v B v BCD v C v  BCD v ABC

№3		D	CD	C
B	1			1
AB	1			1
A

Комментарии.

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

Ответ B

4. Минимизировать функцию

f (x_1,x₂ x_3[x₄)=  ∨  x₃ ∨ x₁ ∨ x₁ x₃

№ 4		x3	x3x4	x3
	1			1
x2
x1	1			1
x1 x2

Решение. Составим карту для 4 переменных

Ответ.

f (x_1,x₂ x_3[x₄)=

5. Минимизировать функцию:

F(x₁ x₂)= x₂ ∨ x₂∨x₁ x₂

№5		x2
		1
x1	1	1

Комментарии.

№6		x3
	1	1
x2
x1	1
x1 x2	1

Составим карту Карно для двух переменных.  Нанесем на карту Карно единицы. Объединим единицы в кон­туры по два элемента. Контуры пересекаются в одной ячейке карты.  Ответ. F(x₁ x₂)= x₁ x₂

6. Минимизировать функцию.

f (x_1,x₂ x_3[)=  ∨  x₃ ∨ x₁ ∨ x₁ x₃

Ответ. f (x_1,x₂ x_3[) =  x₁ ∨

7. Минимизировать функция F(x_1,x₂ x₃),  принимающую значения 1 на наборах 1,2,3,4,5.

2 способ
№6		x3
		1
x2	1	1
x1	1	1
x1 x2

Комментарии.

1способ
№7	x1	x1
x2			1	1
	1	1	1
		x3	x3

1- набор: 001 или  x₃ соответствует 1.

2- набор:010 или   x₂ соответствует 1.

3- набор:011 или   x₂ x₃ соответствует 1.

4- набор:100 или  x₁ соответствует 1.

5- набор:101 или  x₁ x₃ соответствует 1.

Ответ. F(x_1,x₂ x_3[)= x₂∨x₃∨x₁

8. Минимизировать функцию, принимающую значения 1 на наборах:

1). F(x_1,x₂ x₃) – 1,2,3,4,5.                        2). F(x_1,x₂ x₃ х₄) – 1,3,5,6,10

3). F(x_1,x₂ x₃) -  0,4,6,8.               3). F(x_1,x₂ x₃ х₄) – 0,4,11,14,15.

9. Сумма по модулю два, операция двоичного сложения

Таблица истинности
х1	х2,	х1 Å х2
0	0	0
0	1	1
1	0	1
1	1	0

Суммой по модулю два (строгой дизъюн­кцией) двух переменных х, и х₂ называется булева функция х₁ Å х₂, которая равна 1 тогда и только тогда, когда равна 1 только одна переменная..

Функцию "Сумма по модулю два" часто обозначают как М2.

Свойства функции F(x_1,x₂)= х₁ Å х₂

1. Для функции х₁ Å х₂ выполняется  переместительный закон, сочетательный закон, распределительный закон конъюнкции относительно  суммы по модулю два.

2. Операции с константами имеют вид:

xÅx=0            xÅ0=x            x₁Å=1                    x₁ Å1=

3. Возможно разложение в СДНФ:

x₁ Å x₂= x₂∨x₁

4. Для суммы по модулю два справедлива формула отрицания

Å x₂ = x₁Å - справедливость этой формулы можно проверить по таблице истинности.

5. Связь между дизъюнкцией и суммой по модулю два (строгой дизъюнкцией)   x₁ ∨ x₂ =х₁ Å х₂ Å х₁ х₂

6. Конъюнкцию х,х₂ можно выразить через сумму по модулю два и дизъюнкцию по формуле:  х_1}х₂ = х₁ Å х₂ Å (х₁ ∨ x₂), справедливость этой формулы можно проверить по таблице истинности.

7. Сумма по модулю два и операция двоичного сложения в пределах последнего двоичного разряда имеет одинаковую  последова­тельность символов.

0 + 0 =0,         0+1 = 1,          1  + 0=1,         1 + 1 = (1) 0.

Последние свойство  дают основания для применения суммы по модулю два в двоич­ном сумматоре для системы контроля и исправления ошибок. Действительно, если из-за неисправности в схеме один из ар­гументов функции М2 исказится, то одновременно и значение функции изменится на противоположное, что сразу можно будет обнаружить на выходе.

Название "сумма по модулю два" введено из-за следующих соображений:

Обозначим остаток от деления целого числа М на число N  как M mod N.

Рассмотрим множество {0, 1}, причем не абстракт­ных булевых символов, а обычных чисел (в математике его обо­значают Z₂).

Произведем на этом множестве операцию (а + b) mod 2.

Имеем:  (0 + 0) mod 2 = 0,

(1 + 0) mod 2 = (0 + I) mod 2 = 1 mod 2 = 1,

(1 + I) mod 2 = 2 mod 2 = 0.

Очевидно, что операция (а + 6) mod 2 на множестве Z₂ совпадает с нашей строгой дизъюнкцией на мно­жестве В. Поэтому эти множества изоморфны: {Z₂, mod 2} ~ {В, Å }.

Любую булеву функцию можно с помощью операции сложе­ния по модулю два. Для этого в СДНФ надо заменить каждую переменную по формуле  x_i = 1Å x_i и затем упростить ее, используя распределительный закон для конъюнкции относительно  функции М2. Такое представление булевой функции получило название каноническим полигоном  Жегалкина.

Замена СДНФ каноническим полигоном  Жегалкина часто приводит к более простой записи этой функции.

10. Полнота множества функций

Функциональная замкнутость

Обозначим через Р₂ множество всех функций алгебры логики.

Класс функций R Ì Р₂ называется функционально замкнутым, если любая суперпозиция функций этого класса R принадлежит этому же классу. Это означает, что вместе с каждой функцией f (x_1,x₂ x₃) Î R этому классу R принадлежит и функция F(f)

К функционально замкнутым классам относятся такие функции алгебры логики как:

1. Класс функций, сохраняющих константу 0 - Ко. Это функции, для которых выполняется  F(00. ..0) =0.

2. Класс функций, сохраняющих константу 1 - K₁. Это функции, для которых выполняется F(11. .1) = 1.

3. Класс самодвойственных функций - К_с. К нему относятся я функции выполнимо свойство f (x_1,x₂ x₃) = ù f (ùx_1, ùx₂ ùx₃) – число переменных любое.

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

4.  Класс линейных функций (К_л). Функцию алгебры логики называют линейной, если ее канонический полином Жегалкина имеет вид многочлена первой степени. Такие функции похожи  на  алгебраи­ческий  многочлен первой степени.

5. Класс монотонных функций (К_м). Понятие монотонности в алгебре логики трактуется несколько иначе, чем в алгебре.  В данном случае за основу берется понятие "частичный порядок" и понятие сравнимости. Два элемента d и k считаются сравнимыми, если  d предшествует k или k предшествует d. В алгебре логики не все наборы сравнимы. Так наборы 001100 и 001110 сравнимы: у них на первых 4 местах и на 6 месте одинаковы элементы, только в одном месте, именно в данном примере 5 месте различные цифры. Наборы 1100 и 0110 не сравнимы:  у них на двух соответствующих местах разные цифры.

Итак, функция f (х₁х₂...х_/!) называется монотонной, если для любых двух ее сравнимых аргументов, следует сравнимость значений функций.  Функции x_1,x₂ и x₁∨_,x₂ монотонные.

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

Функционально полные системы функций

Систему S функций f₁ ,f₂, ..., f_n алгебры логики называют функционально полной, если любую функцию алгебры логики можно записать с помощью суперпозиции некоторого набора бу­левых функций f₁ ,f₂, ..., f_n

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

Функционально полная система функций называется базисом в пространстве Р_2, если удаление хотя бы одной из функций, входящих в нее, превращает эту систему в функционально не­полную.

Ранее было доказано, что через функции х₁ ∨ х₂, х_} ∧ х₂, ùх можно выразить любые функции алгебры логики, приведя их к виду СКНФ или СДНФ. Следовательно, система этих трех функ­ций полна. Так же мы представляли любую функцию в виде ком­позиции суммы по модулю два, конъюнкции и константы 1 (уда­ление всех 0 приводило к равной функции).

Разумеется это не един­ственные возможности для представления функций алгебры логики. Так, булевы функции можно выразить только через х, v х₂ и ùх, воспользовавшись правилом Де Моргана и представив опе­рацию конъюнкции через дизъюнкцию и отрицание, так как

X_t ∧ Х₂ = ù (ù X₁∧ù Х₂).

Критерий функциональной полноты системы функций сфор­мулирован в теореме Поста - Яблонского.

Теорема. Для того чтобы система S функций f₁ ,f₂, ..., f_n алгебры логики была функционально полной, необходимо и достаточно, чтобы она содер­жала функцию:

~     не сохраняющую константу 0;

~     не сохраняющую константу 1;

~     не являющуюся самодвойственной;

~     не являющуюся линейной;

~     не являющуюся монотонной.

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

Критерии функциональной полноты булевых функций

Функ­ция	F(x1 x2)	Значе­ния	Не сохра­няет 0	Не сохра­няет 1	Не само­двойст­венная	Не линей­ная	Не монотонная
f1	0	0000		+	+
f2	A ¯  B	1000	+	+	+	+	+
f3	x1,	0010		+	+	+
f4		1010	+	+			+
f5	x1Åx2	0110		+	+	+
f6	x1÷x2	1110	+	+	+	+	+
f7	x1 x2	0001			+	+
f8	x1«x2	1001	+		+	+
f9	x2 ®x1	1011	+		+	+
f10	x1Èx2	0111			+	+
f11	1	1111	+		+

Таким образом, для описания булевой алгебры достаточно од­ной функции. Другое дело, что стрелку Пирса и штрих Шеффера трудно интерпретировать в теории множеств и реализовать в виде элементарных логических схем через элементы И - НЕ и ИЛИ - НЕ, а формулы и логические схемы, составленные только из них, являются громоздкими.

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

Примеры основных функционально полных систем булевых функций:

1.Функции: 7,10, 4,  связки и, или, не - лежат в основе алгебры высказываний и булевой алгебры

2. Функции: 4, 7  - связки и, не.

3. Функции: 3, 10 - связки или, не.

4  Функция: 6 - штрих Шеффера,

5. Функция: 2 - стрелка Пирса,

6. Функции: 5, 7, 11 - сумма по модулю два, и, 1.

7. Функции: 3, 4 - x_1,, не.

8. Функции:  9, 4 -  импликация, отрицание.

Заметим, что полная система функций  S₁, являющаяся основой алгебры высказываний  и состоящая из функций 7,10,4  будет избыточной. Действительно, удалив из него одну из функций и выразив их с помощью законов Де Моргана через остальные функции соответственно, можно получить новую функциональ­но полную систему с базисом 5₃ или S₂ соответственно.

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

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

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

Можно построить формальные различные системы - алгеб­ры - в зависимости от выбранных в качестве базисных логиче­ских операций.

Так, булевы функции вида S₁ ={f₇ f ₁₀ f ₄ } образуют булеву алгеб­ру, а операции дизъюнкции, конъюнкции и отрицания образуют базис булевой алгебры.

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

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

Задание 5-14. Переведите предложения на язык алгебры логики и опре­делите, если возможно, их истинность:

а)  каждое слагаемое суммы а + b + с делится на 2;

б)  все простые однозначные числа больше 3 - четные;

в)  хотя бы одно из чисел п, п + 1, п - 1 -- четное;

г)  число а принадлежит по крайней мере одному из множеств А и В;

д)  существует натуральное число х, которое больше 25, но меньше 52 и которое делится на 3 и на 5;

е)  квадратное уравнение имеет не более двух корней.

Задание 5-15. Введя обозначения, запишите логическую форму высказы­ваний и определите их вид:

а)  "Порок - это не употребление плохого, а злоупотребление хорошим" (древняя мудрость);

б)  "Чем честнее человек, тем менее он подозревает других в бесчестности";

в)  "Мастер не учит, а создает ситуации" (древняя мудрость);

г) "Либо все люди должны быть счастливы, либо никто" (Роберт Оуэн);

д)  "Хотите подчинить себе других - начинайте с себя" (Л. Во-венарг);

е)  "Благие намерения без квалификации дают тот же результат, что и квалификация без благих намерений" (В. Леви, психотерапевт).

Задание 5-16. Введя обозначения, запишите логическую форму сложного высказывания, постройте его отрицание, установите семантичес­кую характеристику этих высказываний:

а)  "Не может управлять другим тот, кто не в состоянии управ­лять самим собой" (английская пословица);

б)  "Единственный урок, который можно извлечь из истории, состоит в том, что люди не извлекают из истории никаких уро­ков" (Б. Шоу);

в)  "Со счастьем дело обстоит, как и с часами: чем проще ме­ханизм, тем реже они портятся" (Н.Шамфор);

г) "Чтобы победить противника, не стремись стать сильнее его, а сделай его слабее себя";

д)  "Чем меньше человек собирается сделать, тем больше он об этом говорит";

е) "В жизни возможны лишь две трагедии: не осуществить свою страстную мечту и добиться ее осуществления".

Задание 5-17. Сформулируйте отрицание высказывания и определите истинность данного высказывания и его отрицания:

а) 5 < 3;    б) 5 = 4;     в) если х² = 9, то х = 3;    г) если 5·5=25, то  6<8

Задание 5-18. Установите, какие из следующих пар являются отрицани­ями друг друга, а какие не являются:

а) х > 0 и х < 0;

б) DАВС - прямоугольный и DAВС - тупо­угольный;

в) f(x) - четная функция и f(х) - нечетная функция;

г)  все простые числа нечетные и все простые числа нечетные;

д)  все простые числа нечетные и существуют простые нечет­ные числа;

е) четырехугольник ABCD - квадрат и четырехугольник ABCD - ромб.

Задание 5-19. Из двух простых высказываний А и В составьте сложные высказывания по формулам:  A, A È В, А Å В, А Ç В, А ® В, А « В:

а)  А: "Фигура - ромб"

В: "У фигуры стороны равны";

б)  А: "Сумма цифр числа делится на 3"

В: "Число делится на з";

в)  А: "Треугольник прямоугольный"

В: "Квадрат одной стороны равен сумме квадратов других сторон";

Задание 5-20. Даны простые высказывания А: "Четырехугольник ABCD - параллелограмм", В: "Диагонали четырехугольника ABCD в точке пересечения делятся пополам". Сформулируйте сложные вы­сказывания по формулам и определите их истинность по таблице. Упростите высказывания и сравните их таблиць1_истинности-

а) А ®В;          б) В « А;      в) А Å В;        г) А Ç В;        д) В È  А.

е)  произведение двух положительных чисел положительно;

Задание 5-21. Для данной импликации сформулируйте обратную, про­тивоположную и противоположную обратной. Какие из этих че­тырех импликаций истинные, а какие ложные?

а)  если число делится на 9, то сумма его цифр делится на 3;

б) если диагонали параллелограмма равны, то это прямоуголь­ник;

в)  если натуральное число делится на 3 и на 5, то оно делится на 15;

д)  площади равных фигур равны;

е)  произведение трех отрицательных чисел отрицательно.

Контрольные вопросы и задания

1. Понятие суждения и высказывания.
2. Правила построения составных высказываний.
3. Что собой представляет булева алгебра
4. Назовите булевы функции для двух аргументов
5. Привести физическую и графическую интерпретацию логических операций
6. Понятия "необходимо" и "достаточно".
7. Виды теорем и связь между ними.
8. Законы алгебры логики.
9. Понятие элементарных и нормальных форм
10. Понятие терма.
11. Что означает минимизировать функцию
12. Способы минимизации функций логики.
13. Сумма по модулю два и ее связь с логическими операциями
14. Понятие полноты множества функций

Контрольная работа 5-1

Вариант 1

1. Какие из предложений являются высказываниями:

а).  Умение грамотно использовать логические операции повы­шает уровень  программирования.

б).  Знание математической логики необходимо любому специа­листу.

2. Установите истинность высказываний:

а).   A: "В классе присутствуют 25 учащихся".   б).  M:  "p, s, v- буквы греческого алфавита".

3. Дать определения   и построить таблицы истинности:

а).  Конъюнкции;  б). Импликации.

4. Составить таблицы истинности высказываний.

а).                                     б).

5. Установить справедливость равенства (A+B & C)+A=A & B+(ùC+A)

Вариант 2

1. Какие из предложений являются высказываниями

а).  История логики насчитывает около двух с половиной тыся­челетий.

б).  Математическая логика - увлекательная наука

2. Установите истинность высказываний:

а).  D:  "1‰ – один промилле составляет тысячную долю числа"             б).  Q:  "p » 3,14"

3. Дать определения   и построить таблицы истинности:

а). Дизъюнкции;  б).  Эквиваленции.

4. Составить таблицы истинности высказываний

а).                       б).

5. Установить справедливость равенства (A+B = (A+B) & (A+ ùB)

Требования к знаниям умениям и навыкам.

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

---

[1] Логика возникла в 384-322г до новой эры – Аристотель. В этой области работали Лейбниц.-17в, Дж. Буль – 18в. Бурно развивается в современном мире.

[2] Булевы функции и переменные будут рассмотрены в последующих главах.