Основы математической логики (Учебное пособие)


ГБОУ СПО «АМТ» КК
Учебное пособие
Основы математической логики
для обучающихся специальности
«Программирование в компьютерных системах»
Автор: Беляева Татьяна Юрьевна
Содержание
1. Высказывания и операции над ними 4
1.1. Понятие высказывания. Истинностные значения высказываний 4
1.2. Логические операции над высказываниями 5
2. Формулы алгебры высказываний 7
2.1. Понятия логической формулы и ее ранга 7
2.2. Правила чтения формул 8
2.3. Составление таблиц истинности для формул 8
2.4. Классификация формул. Понятие о их равносильности 9
3. Основные равносильности алгебры высказываний 10
4.
4.1. Логические законы и их применение при формулировании и доказательстве теорем
Законы логики, используемые в умозаключениях 12
12
4.2. Понятие о теоремах. Прямая, обратная и противоположная теоремы. Необходимые и достаточные условия 13
4.3. Методы доказательств теорем 15
5. Функции алгебры логики. Булева алгебра 16
5.1. Понятие логической функции 16
5.2. Некоторые примеры логических функций 17
5.3. Отображение булевых функций п переменных на единичный п-мерный куб 19
5.4. Совершенные нормальные формы булевых функций и приведение к ним 20
5.5. Зависимости между булевыми функциями 22
5.6. Минимизация булевых функций. Карты Карно 23
5.7. Канонический многочлен Жегалкина. Методика представления булевой функции в виде многочлена Жегалкина 26
5.8. Приложение логических функций к анализу и синтезу релейно-контактных схем. Логические схемы 28
6. Логика предикатов 33
6.1. Основные понятия, связанные с предикатами 33
6.2. Логические операции над предикатами 35
6.3. Кванторные операции над предикатами 38
6.4. Понятие предикатной формулы. Основные равносильности логики предикатов 41
Задания для самостоятельного решения 44
Контрольные вопросы 47
Тест для самоконтроля 49

1. Высказывания и операции над ними
1.1. Понятие высказывания. Истинностные значения высказываний
Опр. Высказыванием называется такое повествовательное предложение, для которого имеет смысл говорить, истинно оно или ложно, и которое не является одновременно истинным и ложным.
Обозначение: А, В, С, … (возможно, с индексами)
Опр. Истина и ложь называются истинностными значениями высказываний.
Если истину обозначить единицей, а ложь – нулем, то можно говорить, что значение истинности высказывания равно 1 или 0.
Напр.: А = «параллелограмм имеет 4 вершины» - истинное высказывание
В = «зимой день короче, чем летом» - истинное высказывание
С = «2 · 2 = 5» - ложное высказывание
К = «сегодня идет дождь и дует ветер» - высказывание с переменным истинностным значением (в какой-то момент оно может оказаться истинным, а в какой-то – ложным)
(!!)1 В соответствии с определением, вопросительные и восклицательные предложения, просьбы, приветствия высказываниями не являются.
(!!)2 При работе с высказываниями совершенно не важно их конкретное содержание, интерес имеет лишь их значение истинности.
Опр. Высказывания А и В называются равносильными, если они имеют одинаковые истинностные значения.
Обозначение: А ≡ В
Напр.: «2 · 2 = 4» ≡ «Волга впадает в Каспийское море»
Таким образом, все истинные высказывания неразличимы и отождествляются с их значением «истина». Символическое высказывание, которому не приписано какое-либо конкретное содержание, но о котором известно, что оно истинно, принято обозначать английской буквой Т. Аналогично все ложные высказывания отождествляются с их значением «ложь». Символическое ложное высказывание обозначают буквой F.
Так, А ≡ Т, В ≡ Т, С ≡ F. Высказывание К не равносильно ни Т, ни F.
Из сказанного следует, что можно говорить об отображении совокупности всех высказываний на множество, состоящее из 2-х элементов, один из которых носит название истины (равен 1), другой – лжи (равен 0).
Целесообразно различать 2 типа высказываний: простые и сложные.
Опр. Высказывание называется простым, если никакая его часть сама не является высказыванием. Если это условие не выполняется, то высказывание называется сложным.
Так, А – простое высказывание, К – сложное высказывание
Сложные высказывания получаются из простых при помощи логических операций (связок).
1.2. Логические операции над высказываниями
I. Отрицание высказывания
Опр. Отрицанием высказывания А называется сложное высказывание А (читается «не А», «неверно, что А»), которое истинно тогда и только тогда, когда А ложно, и ложно, когда А истинно.
Другие обозначения: А, А′, ~А, ¬ А, NOT A
Эту операцию можно определить с помощью ее таблицы истинности:
А А1 0
0 1
Напр.: Пусть А = «сегодня светит солнце», тогда А = «сегодня солнце не светит»
II. Конъюнкция 2-х высказываний (логическое умножение)
Опр. Конъюнкцией 2-х высказываний А и В называется сложное высказывание А /\ В (читается «А и В»), которое истинно лишь тогда, когда оба высказывания истинны.
Другие обозначения: А & B, А · B, А AND B
A B A /\ B
1 1 1
1 0 0
0 1 0
0 0 0
Напр.: А = «Сегодня светит солнце», В = «Температура повышается»
A /\ B = «Сегодня светит солнце и температура повышается»
(!!) Конъюнкция позволяет связывать любое конечное число высказываний. Их конъюнкция истинна, когда истинно каждое из них, и ложна, когда ложно хотя бы одно из них.
III. Дизъюнкция 2-х высказываний (логическое сложение)
Опр. Дизъюнкцией 2-х высказываний А и В называется сложное высказывание А \/ В (читается «А или В»), которое ложно тогда и только тогда, когда оба высказывания ложны.
Другие обозначения: А + B, А OR B
A B A \/ B
1 1 1
1 0 1
0 1 1
0 0 0
Напр.: А = «Вечером я читаю книгу», В = «Вечером я смотрю телевизор»
А \/ В = «Вечером я читаю книгу или смотрю телевизор»
Опр. Дизъюнкцией 2-х высказываний А и В в исключающем смысле называется сложное высказывание А \/ В (читается «или А, или В»), истинность которого определяется следующей таблицей:
A B A \/ B
1 1 0
1 0 1
0 1 1
0 0 0
373951513208000Другие обозначения: А ∇ B, А ХOR B, А В
Напр.: А = «После окончания школы я поеду учиться в Москву»,
В = «После окончания школы я поеду учиться в Питер»
А \/ В = «После окончания школы я поеду учиться или в Москву, или в Питер»
IV. Импликация 2-х высказываний
Опр. Импликацией 2-х высказываний А и В называется сложное высказывание А → В (читается «если А, то В», «из А следует В»), которое ложно, если А – истинно, а В - ложно.
Другие обозначения: А => B, А IMP B
A B A → B
1 1 1
1 0 0
0 1 1
0 0 1
Напр.: А = «Сегодня светит солнце», В = «Сегодня нет дождя»
А → В = «Если сегодня светит солнце, то нет дождя»
V. Эквиваленция 2-х высказываний
Опр. Эквиваленцией 2-х высказываний А и В называется сложное высказывание А ↔ В (читается «А тогда и только тогда, когда В», «А эквивалентно В», «А необходимо и достаточно для В»), которое истинно только тогда, когда высказывания имеют одинаковые истинностные значения.
Другие обозначения: А< => B, А ~ B, A ECV В
A B A ↔B
1 1 1
1 0 0
0 1 0
0 0 1
Напр.: А = «Число делится на 3», В = «Сумма цифр числа делится на 3»
А ↔ В = «Число делится на 3 т. и т. т., к. сумма его цифр делится на 3»
2. Формулы алгебры высказываний
2.1. Понятия логической формулы и ее ранга
Опр. Высказывание с заданным значением истинности называется логической постоянной (F и Т), а высказывание, значение истинности которого не задано, называется логической переменной.
Опр. Всякое простое высказывание (логическая переменная или логическая постоянная), а также всякое сложное высказывание, образованное из простых с помощью логических операций, называется логической формулой.
Обозначение: Ф, Ф1, Ф2, … Если в формулу Ф входят высказывания Х1, Х2,…, Хп, то в общем виде формулу обозначают Ф(X1, Х2,…, Xn).
Напр.: 1) Ф1 = А ˅ В ˄ (С → А)
2) Ф2 = ((А → У) ˄ В) ↔ (Х ˅ У)
Опр. Рангом формулы A называется число всех логических операций, с помощью которых эта формула образована.
Обозначение: r (Ф)
Так, r (Ф1) = 4, r (Ф2) = 5
(!!) Очевидно, что ранг простого высказывания равен нулю.
2.2. Правила чтения формул
Если скобки отсутствуют, то логические операции выполняются в следующей очередности: отрицание, конъюнкция, дизъюнкция, импликация и эквиваленция.
Если без скобок записаны друг за другом несколько одинаковых операций, то они выполняются последовательно слева направо.
Операция отрицания записывается без скобок и применяется ко всей формуле, записанной под символом отрицания.
При необходимости изменить естественный порядок действий часть формулы заключается в скобки.
Укажем порядок действий для формулы (А ˅ В →С) ˄ А: 1) В; 2) А ˅ В; 3) А ˅ В; 4) А ˅ В →С; 5) (А ˅ В →С) ˄ А
Вычислим значение этой формулы при А = 1, В = С = 0.
Ф(1, 0, 0) = (1 ˅ 0 →0) ˄ 1 = (1 ˅ 1 →0) ˄ 1 = (1 →0) ˄ 1 = (0 →0) ˄ 1 = 1 ˄ 1 = 1.
2.3. Составление таблиц истинности для формул
Если для данной формулы необходимо вычислить ее значения при всевозможных наборах значений логических переменных, то составляют таблицу истинности. Такая таблица всегда имеет 2п строк, где п – число входящих в формулу переменных.
ПР. Постройте таблицы истинности для формул: а) А ˄ A; б) А ˅ (В→А).
а)
А AА ˄ A1 0 0
0 1 0
б)
А В ВВ→АА ˅ В→А1 1 0 1 1
1 0 1 1 1
0 1 0 1 1
0 0 1 0 0
2.4. Классификация формул. Понятие о их равносильности
Опр. Формула Ф(X1,…, Xn) называется выполнимой, если она принимает значение 1 хотя бы при одном наборе значений Х1,…, Хп.
Опр. Формула Ф(X1,…, Xn) называется тождественно истинной (законом логики), если она принимает значение 1 при любом наборе значений Х1,…, Хп.
Напр.: Х ˅ ХОпр. Формула Ф(X1,…, Xn) называется тождественно ложной (противоречием), если она принимает значение 0 при любом наборе значений Х1, …, Хп.
Напр.: Х ˄ ХОпр. Две формулы Ф1 и Ф2 называется равносильными, если они принимают одинаковые значения при каждом наборе значений Х1, Х2, …, Хп.
Обозначение: Ф1 ≡ Ф2
Решить вопрос о равносильности формул можно с помощью их истинностных таблиц.
ПР. Докажем две равносильности, которые следует помнить.
Х → У ≡ Х ˅ У
Х У Х→У ХХ ˅ У
1 1 1 0 1
1 0 0 0 0
0 1 1 1 1
0 0 1 1 1
Х↔У ≡ Х ˅ У ˄ Х ˅ У
Х У Х↔У УХ ˅ УА ХХ ˅ У
В А ˄ В
1 1 1 0 1 0 1 1
1 0 0 1 1 0 0 0
0 1 0 0 0 1 1 0
0 0 1 1 1 1 1 1
(!!) Так как импликацию и эквиваленцию можно выразить через операции отрицания, конъюнкции и дизъюнкции, то любую формулу можно записать, используя только три логических символа.
3. Основные равносильности алгебры высказываний
Операции конъюнкция и дизъюнкция коммутативны:
А ˄ В ≡ В ˄ А
А ˅ В ≡ В ˅ А
Операции конъюнкция и дизъюнкция ассоциативны:
(А ˄ В) ˄ С ≡ А ˄ (В ˄ С)
(А ˅ В) ˅ С ≡ А ˅ (В ˅ С)
Операции конъюнкция и дизъюнкция связаны между собой свойством дистрибутивности:
А ˄ (В ˅ С) ≡ А ˄ В ˅ А ˄ С
А ˅ (В ˄ С) ≡ (А ˅ В) ˄ (А ˅ С)
Свойства логических констант:
А ˄ Т ≡ А А ˄ F ≡ F
А ˅ Т ≡ T А ˅ F ≡ A
Законы де Моргана:
А ˄ В ≡ А ˅ В А ˅ В ≡ А ˄ ВСвойства отрицания:
А ˄ A ≡ F А ˅ A ≡ T
T≡F F≡T A ≡A Законы идемпотентности (простого поглощения):
А ˄ А ≡ А А ˅ А ≡ А
Равносильность, отменяющая импликацию:
А → В ≡ A ˅ В
Равносильности, отменяющие эквиваленцию:
А ↔ В ≡ (А ˅ В) ˄ (А ˅ В)
А ↔ В ≡ А ˄ В ˅ А ˄ В Равносильности, отменяющие исключающую дизъюнкцию:
А \/ В ≡ А ˄ В ˅ А ˄ В (!!) Все приведенные свойства можно доказать с помощью истинностных таблиц.
Они, в свою очередь, позволяют получить ряд других важных законов и тождеств уже без обращения к таблицам истинности, а с помощью так называемых равносильных преобразований.
Рассмотрим некоторые из них.
Законы поглощения (расширенные):
А ˄ (А ˅ В) ≡ А
Доказательство:
А ˄ (А ˅ В) ≡ (А ˅ F) ˄ (А ˅ В)≡ А ˅ (F ˄ B) ≡ А ˅ F ≡ A, ч.т.д.
А ˅ (А ˄ В) ≡ А
Доказательство: (самостоятельно)
Закон объединения посылок:
А → (В → С) ≡ А ˄ В → С
Доказательство:
А → (В → С) ≡ А ˅ (В ˅ С) ≡ (А ˅ В) ˅ С ≡ А ˄ В ˅ С ≡ А ˄ В → С, ч.т.д.
Закон перестановки посылок:
А → (В → С) ≡В → (А → С) Закон отрицания импликации:
А→В ≡А ˄ В
Закон исключения отрицаний в эквиваленции:
А ↔ В ≡А ↔ В
Закон переноса отрицания в эквиваленции:
А ↔ В ≡А ↔ В
Законы исключения конъюнкции и дизъюнкции:
А ˄ В ≡ А ˅ В А ˅ В ≡ А ˄ В
Зная рассмотренные выше тождества, можно упрощать логические формулы с помощью так называемых равносильных преобразований.
ПР. Упростите формулу с помощью равносильных преобразований:
P → P ˅ Q
/ P → P ˅ Q ≡ P ˅ P ˅ Q ≡ (P ˅ P) ˅ Q ≡ T ˅ Q ≡ T /
X→Y ˅ X ˅ Y/ X→Y ˅ X ˅ Y ≡ (X ˄ Y) ˅ X ˅ Y ≡ (X ˅ X) ˄ (Y ˅ X) ˅ Y ≡ T ˄ (Y ˅ X) ˅ Y ≡ (Y ˅ X) ˅ Y ≡ (Y ˅ Y) ˅ X ≡ T ˅ X ≡ T /
(P ˄ Q ˄ S) ˅ (P ˄ S) ˅ (Q ˄ S)
/ (P ˄ Q ˄ S) ˅ (P ˄ S) ˅ (Q ˄ S) ≡ (P ˄ Q ˄ S) ˅ (P ˅ Q ) ˄ S ≡ (P ˄ Q ˄ S) ˅ P ˄ Q ˄ S ≡ S ˄ (P ˄ Q ˅ P ˄ Q ) ≡ S ˄ T ≡ S /
X ˅ Y→X ˅ Y/ X ˅ Y→X ˅ Y ≡ X ˅ Y˅ X ˅ Y ≡ X ˅ Y˄ (X ˅ Y) ≡X↔Y /

4. Логические законы и их применение
при формулировании и доказательстве теорем
4.1. Законы логики, используемые в умозаключениях
Закон тождества: Каждая мысль, приводимая в данном умозаключении, при повторении должна иметь одно и то же устойчивое содержание: А → А
Закон противоречия: не могут быть истинными две противоположные мысли об одном и том же предмете, взятом в одно и то же время и в одном и том же отношении: А ˄ А
Закон исключенного третьего: из 2-х противоречащих высказываний в одно и то же время и в одном и том же отношении одно непременно истинно: А ˅ А
Закон двойного отрицания: отрицание отрицания любого высказывания равносильно самому высказыванию: А↔А
Закон «из ложного что угодно»: ложное высказывание имплицирует любое высказывание: А→(А→В)Закон «modus ponens» (утверждающий модус, модус – философский термин, означающий свойство предмета, присущее ему не постоянно, а лишь в некоторых условиях): если истинна некоторая импликация и, кроме того, истинна посылка этой импликации, то истинно и ее следствие: А ˄ (А → В) → В
Закон «modus tollens» (отрицающий модус): если истинна некоторая импликация и, кроме того, ложно следствие этой импликации, то ложна и ее посылка: (А → В) ˄ В→ АЗакон силлогизма: Отношение «имплицировать» между высказываниями транзитивно (силлогизм – это умозаключение, в силу которого, признав истинность посылок, нельзя не согласиться с истинностью заключения, вытекающего из посылок): (А → В) ˄ (В → С) (А → С)
Закон контрапозиции (противопоставления): «Когда два явления так относятся друг к другу, что, если есть одно, необходимо есть и другое, то если второго нет, не будет и первого» Аристотель: (А → В) ↔ (В→А)
Понятие о теоремах. Прямая, обратная и противоположная
теоремы. Необходимые и достаточные условия
Опр. Теорема – это некоторая импликация высказываний, т.е. Т ≡А →ВПри этом высказывание А называется условием теоремы, а В – ее заключением.
Если в теореме А и В простые высказывания, то теорема называется простой, в противном случае - сложной.
Пусть Т ≡А →В (1) – некоторая теорема (прямая), тогда:
теорема Тоб. ≡В →А (2) называется обратной теоремой;
теорема Тпр. ≡А →В (3) называется противоположной теоремой;
теорема Т пр.об. ≡В →А (4) называется теоремой, противоположной к обратной.
Напр.:
1) Пусть Т – «Если четырехугольник является прямоугольником, то его диагонали равны», тогда
Тоб - «Если в четырехугольнике диагонали равны, то четырехугольник является прямоугольником»
Тпр. - «Если четырехугольник не является прямоугольником, то его диагонали не равны»
Т пр.об. – «Если в четырехугольнике диагонали не равны, то четырехугольник не является прямоугольником»
В рассмотренном примере теоремы (1) и (4) являются одновременно истинными, а теоремы (2) и (3) одновременно ложными. Контрпримером к теореме (2) является равнобочная трапеция.
(!!) Можно доказать, что Т ≡ Т пр.об. и Тоб. ≡ Тпр., а это значит, что, если доказана теорема (1), то доказана и теорема (4), а если доказана теорема (2), то доказана и теорема (3).
2) Рассмотрим пример сложной теоремы: «Если у двух треугольников АВС и А1В1С1 ⦟А = ⦟А1 и ⦟В = ⦟В1, то треугольники подобны»
Эта теорема имеет следующую структуру: А В → С
Обратная ей теорема: С → А В
Противоположная: А В→ С ≡ А В →С
Противоположная к обратной: С → А В
Очевидно, что все четыре теоремы истинные.
Т.к. формулу, выражающую сложную функцию, можно преобразовать в другую с помощью равносильных преобразований, то и формулировки у одной и той же теоремы могут быть различными, а значит, обратных и противоположных теорем у сложной теоремы может быть несколько.
Если истинна теорема А →В, то условие А называют достаточным для В, а В – необходимым для А. 0 при этом истина и теорема В → А, то А будет необходимо для В. В этом случае говорят, что А необходимо и достаточно для В, и формулируют теорему в виде А ↔ В (А тогда и только тогда, когда В).
Напр.: признак делимости на 3
4.3. Методы доказательств теорем
I. Схемы прямого доказательства
Известно, что истинность любой теоремы устанавливается путем доказательства, т.е. последовательного выведения одних суждений из других, истинность которых задана или доказана ранее. Существуют конкретные способы этого выведения. Рассмотрим некоторые из них:
1. Правило заключения: Если истинны формулы (утверждения) А и А → В, то будет истинна формула В.
А → В
А
В 2. Правило введения конъюнкции: Если истинны формулы (утверждения) А и В, то истинна и их конъюнкция.
А
В
А В3. Правило удаления конъюнкции: Если истинна конъюнкция 2-х формул (утверждений), то каждая из них истинна.
А В А В
А В 4. Правило контрапозиции: Если утверждение А имплицирует утверждение В, то отрицание В имплицирует отрицание А.
А → В
В→А5. Закон силлогизма: Если из формулы А следует формула В , а из формулы В следует формула С, то из А следует В.
А → В
В → С
А→ С6. Правило доказательства разбора случаев:
А → С А → С
В → С А → D
А В → С А → С DII. Доказательство теорем методом от противного
Чтобы доказать теорему Т ≡А →В методом от противного предполагают, что Т – ложное высказывание, т.е. Т – истинное высказывание. Из этого предположения извлекают логические следствия, среди которых есть следствие S, которое:
- либо тождественно ложно,
- либо противоречит условию теоремы,
- либо противоречит аксиоме данной теории или теореме, истинность которой уже установлена,
- либо противоречит какому-либо другому следствию этой теоремы.
Если такое следствие найдено, то делают вывод, что Т, в действительности, ложное высказывание, т.е. теорема Т истинна.
5. Функции алгебры логики. Булева алгебра
5.1. Понятие логической функции
Известно, что значение формулы алгебры логики полностью зависит от значений входящих в эту формулу переменных высказываний. С этой точки зрения формулу логики можно назвать функцией входящих в нее простых высказываний.
Опр. Логической (булевой) функцией п переменных f(х1,…,хп) называется функция, каждая переменная которой может принимать 2 значения (0 и 1), и при этом сама функция принимает только одно значение (0 или 1).
Опр. Переменная хi в функции f(х1,х2,…,хп) называется несущественной (фиктивной), если изменение значения хi в любом наборе значений переменных не меняет значения функции, т.е. f(х1,…,хi-1,0, хi+1,…,хп) = f(х1,…,хi-1,1, хi+1,…,хп).
В этом случае функция f(х1,х2,…,хп) по существу зависит от п-1 переменной, т.е. представляет собой функцию g(х1,…,хi-1,хi+1,…,хп) от п-1 переменной. Говорят, что функция g получена из функции f удалением фиктивной переменной, а функция f получена из g введением фиктивной переменной.
(!!) Две равносильные формулы логики выражают одну и ту же функцию.
(!!) Существует 22пбулевых функций п переменных.
5.2. Некоторые примеры логических функций
I. Логические функции одной переменной
Таких функций – четыре. Приведем их в таблице:
x φ0φ1φ2φ31 0 1 0 1
0 0 0 1 1
Функции φ0и φ3 – это постоянные функции (константы: 0 и 1 соответственно). Их значения не зависят от значений переменной х, и, следовательно, переменная х для них несущественна. Т.о., φ0х= 0, φ3х= 1.Функция φ1 «повторяет» х, т.е. φ1х= х.Функция φ2 «отрицает» х, т.е. φ2х= х. Эту функцию называют отрицанием (или функцией НЕ).
II. Логические функции двух переменных
Таких функций – шестнадцать. Приведем их в таблице:
Х1 Х2 01234567891011121314151 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
Функции0и 15 – константы 0 и 1, т. е. функции с 2-мя несущественными переменными: 0(х1, х2) = 0, 15(х1, х2) = 1
Функция 3(х1, х2) = х1 – функция первого аргумента
Функция 5(х1, х2) = х2 – функция второго аргумента
Функция 12(х1, х2) = х1 – функция инверсии первого аргумента
Функция 10(х1, х2) = х2 – функция инверсии второго аргумента
В функциях 3 и 12 переменная х2 фиктивна, а в функциях 5 и 10 – х1
Функция 1(х1, х2) = х1 х2 называется логическим умножением (функцией И)
Функция 7(х1, х2) = х1 х2 называется логическим сложением (функцией ИЛИ)
Функция 14(х1, х2) = х1 х2 = х1 / х2 – это функция Шеффера (отрицание конъюнкции или штрих Шеффера)
Функция 8(х1, х2) = х1 х2 = х1 ↓ х2 – это функция Пирса (отрицание дизъюнкции или стрелка Пирса)
Функция 9(х1, х2) = х1 ↔ х2 называется равнозначностью
Функция 6(х1, х2) = х1↔х2– это неравнозначность (сложение по модулю 2)
Остальные функции специальных названий не имеют. Это функции:
13(х1, х2) = х1 → х2 ; 2(х1, х2) = х1 → х2 11(х1, х2) = х2 → х1 ; 4(х1, х2) = х2 → х1Таким образом, из шестнадцати функций 2-х переменных шесть функций имеют фиктивные переменные. С ростом числа переменных доля функций, имеющих фиктивные переменные, убывает и стремится к нулю.
5.3. Отображение булевых функций п переменных
на единичный п-мерный куб
Область определения булевых функций п переменных f(х1,…,хn) можно рассматривать как совокупность п –мерных векторов, координатами которых являются числа 0 и 1.
Например, при п = 3 область определения – есть совокупность 8-и трехмерных векторов (0; 0; 0), (0; 0; 1),…, (1; 1; 1). При этом каждый вектор можно представить вершиной единичного трехмерного куба:
1377315-3238500 х3
001 011
1129665-1905001758315-1905002034540-1905001377315-190500
112966579375001129665793750017583157937500 101 111
17583151987550078676519875500137731519875500 000 010 х2

11296658572500 100 110
х1
В общем случае совокупность векторов отображается на множество вершин п-мерного куба. Все такие вершины образуют логическое пространство.
Булева функция отображается на п-мерном единичном кубе путем выделения тех вершин, которые соответствуют векторам, на которых эта функция принимает значение 1. Эти вершины принято выделять жирными точками или другим цветом
ПР. Отобразите булеву функцию 3-х переменных f(x1, x2, x3) = (x1 x2) (x2 → x3) на единичный 3-хмерный куб.
x1 x2 x3 x1 x2 x3x2 → x3f
1 1 1 1 0 0 0
1 1 0 1 1 1 1
1 0 1 1 0 1 1
1 0 0 1 1 1 1
0 1 1 1 0 0 0
0 1 0 1 1 1 1
0 0 1 0 0 1 0
0 0 0 0 1 1 0
1397000-317500 х3

1129665-1905001758315-1905002034540-1905001377315-190500
112966579375001129665793750017583157937500
17583151987550078676519875500137731519875500 х2

11296658572500
х1
5.4. Совершенные нормальные формы булевых функций
и приведение к ним
Если логическая формула представлена в виде конъюнкции дизъюнкцийдизъюнкции конъюнкций простых высказываний и их отрицаний, то говорят, что она задана в конъюнктивной дизъюнктивной нормальной форме (КНФ)(ДНФ).
Напр.: (В ˄ A) ˅ (А ˄ В ˄ С) – ДНФ
(В ˅ A) ˄ (В ˅ С) ˄ (А ˅ В ˅ С) – КНФ
(!!) Всякую логическую формулу, а значит, и любую булеву функцию можно записать в разных нормальных формах.
Напр.: f(x1,x2,x3) = х1 ˄ (х2 ˅ х3) – КНФ
f(x1,x2,x3) = (х1 ˄ х2) ˅ (х1 ˄ х3) – ДНФ
Если в каждом слагаемом (сомножителе) нормальной формы представлены все переменные (либо сами, либо их отрицания), то она называется совершенной нормальной формой (СДНФ, СКНФ).
Напр.: (А ˅ В ˅ С) ˄ (A ˅ В ˅ С) ˄ (А ˅ В ˅ С) – СКНФ
(!!) Всякую логическую функцию можно единственным образом представить в виде СДНФ и СКНФ. Исключение составляют логические константы: «1» не имеет СКНФ, а «0» не имеет СДНФ.
Алгоритмы представления произвольной булевой функции,
Заданной таблицей истинности, в виде СДНФ и СКНФ
Если функция f(x1,…,xn) задана таблицей истинности, то для каждого набора значений переменных, на котором функция принимает значение 1, запишем конъюнкцию переменных либо их отрицаний: в качестве члена конъюнкции возьмем саму переменную xк, если ее значение в данном наборе равно 1, и отрицание xк, если равно 0. Дизъюнкция всех таких конъюнкций и даст нам искомую формулу.
ПР. Рассмотрим таблицу истинности функции 3-х переменных:
x1 x2 x3 f(x1,x2,x3)
1 1 1 1
1 1 0 0
1 0 1 1
1 0 0 0
0 1 1 0
0 1 0 1
0 0 1 1
0 0 0 0
Согласно изложенному алгоритму получим СДНФ:
f(x1,x2,x3) = x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3
Для получения СКНФ весь алгоритм меняется с точностью до «наоборот». Составим для приведенного выше примера СКНФ:
(x1 x2 x3) ( x1 x2 x3) (x1 x2 x3) (x1 x2 x3)
ПР. Записать в СКНФ функцию Пирса f(x1,x2) = x1 ↓ x2
x1 x2 x1 ↓ x2
1 1 0
1 0 0
0 1 0
0 0 1

f(x1,x2) = (x1 x2) (x1 x2) (x1 x2)
Представление булевых функций в совершенной форме
с помощью равносильных преобразований
ПР.1. Пусть булева функция задана в ДНФ:
f (x,y,z) = (x y z) (x y).
Преобразуем ее в СДНФ.
/ f (x,y,z) = (x y z) (x y T) = (x y z) (x y ( z z)) = (x y z) (x y z) (x y z)/
ПР.2. Преобразовать КНФ в СКНФ для функции
f(х1, х2, х3) = (х1 х2) (х1 х2) (х1 х2 х3)
/ f(х1, х2, х3) = (х1 х2 F) (х1 х2 F) (х1 х2 х3) = (х1 х2 (х3 х3)) (х1 х2 х3 х3) (х1 х2 х3) = (х1 х2 х3) (х1 х2 х3) (х1 х2 х3) (х1 х2 х3) (х1 х2 х3) = (х1 х2 х3) (х1 х2 х3) (х1 х2 х3) (х1 х2 х3) /
5.5. Зависимости между булевыми функциями
Все булевы функции можно выразить через две операции: отрицание и конъюнкцию или отрицание и дизъюнкцию. Более того, для записи любой булевой функции достаточно только одной из двух элементарных функций: стрелки Пирса или штриха Шеффера.
Покажем это на примерах:
1) Функция отрицания
х = х х = х / х
х = х х = х ↓ х
2) Функция конъюнкции
х1 х2 = х1 х2 = х1/ х2 = (х1 / х2) / (х1 / х2)
х1 х2 = х1 х2 = х1 х2 = х1 ↓ х2 = (х1 ↓ х1) ↓ (х2 ↓ х2)
3) Функция дизъюнкции
х1 х2 = х1 х2 = х1 х2 = х1 / х2 = (Х1 / Х1) / (Х2 / Х2)
х1 х2 = х1 х2 = х1↓х2 = (Х1↓Х2) ↓ (Х1↓Х2)
4) Функция импликации
х1 → х2 = х1 х2 = х1 х2 = х1 / х2 = х1 / (х2 / х2)
х1 → х2 = х1 х2 = х1 ↓ х2 = х1↓х1↓х2 = ((х1 ↓ х1) ↓х2) ↓ ((х1 ↓ х1) ↓х2)
5.6. Минимизация булевых функций. Карты Карно
Сложность логической функции пропорциональна числу переменных и числу логических операций. Логические функции можно упростить непосредственно с помощью логических тождеств, но, как правило, такие преобразования требуют громоздких выкладок. К тому же процесс упрощения булевых выражений не является алгоритмическим. Поэтому более целесообразно использовать специальные алгоритмические методы минимизации, позволяющие проводить упрощение функции более просто, быстро и безошибочно. Наиболее часто используемыми из них являются метод карт Карно и метод Квайна-Мак-Класки.
Метод карт Карно используют на практике при числе переменных не более шести. Если переменных больше шести, обычно используют метод Квайна-Мак-Класки, т.к. метод карт теряет свою наглядность.
Карты Карно является графическим способом минимизации булевых функций, который представляет собой операции попарного неполного склеивания и элементарного поглощения.
Операция попарного склеивания осуществляется между двумя членами (термами), содержащими одинаковые переменные, вхождения которых совпадают для всех переменных, кроме одной. В этом случае все переменные, кроме одной, можно вынести за скобки, а оставшиеся в скобках прямое и инверсное вхождение одной переменной подвергнуть склейке.
Например: х1˄х2˄х3˄х4˅х1˄х2˄х3˄х4=х1˄х2˄х4˄(х3˅х3) = х1˄х2˄х4Таким образом, главной задачей при минимизации СДНФ и СКНФ является поиск термов, пригодных к склейке с последующим поглощением, что для больших форм может оказаться достаточно сложной задачей. Карты Карно предоставляют наглядный способ отыскания таких термов.
С одной стороны, карты Карно можно рассматривать как перестроенные соответствующим образом таблицы истинности функций, а с другой - как определенную плоскую развертку единичного n-мерного (булевого) куба.
Число клеток карты равно 2ⁿ, где n - число переменных функции. Ее столбцы и строки обозначаются прямыми и инверсными переменными данной функции таким образом, чтобы любые соседние клетки по строкам или по столбцам отличались бы между собой значением только одной переменной. Это сделано для того, чтобы было бы возможно применить закон склеивания. Клетки, находящиеся на границах одной строки или столбца, так же считаются соседними. Каждая клетка карты соответствует произведению переменных, на пересечении которых она находится.
Карты Карно для 2-х, 3-х и 4-х переменных можно изобразить на плоскости. Они имеют вид:
х2 х2х1 х1х2 х2 х2х2х1 х1х3 х3х3х3
х2 х2 х2х2х1 х3
х1 х3х1х3х1х3
х4 х4х4х4 Для 5-и и более переменных необходимы объемные фигуры.
ПР. Пусть функция 2-х переменных задана таблицей истинности:
х1 x2 f
1 1 1
1 0 1
0 1 0
0 0 0
СДНФ: f = x1˄х2˅x1˄х2Составим для этой функции карту Карно:
х2 х2х1 1 1
х10 0
Для минимизации функций используется закон «склеивания»:
x1˄ х2˅x1˄ х2=х1Если переменная изменяет свое значение, а функция при этом остается неизменной, то эту переменную можно исключить из выражения.
Для получения минимальной функции охватывают областями все клетки, имеющие значение 1 и являющиеся соседними. Объединяются клетки по следующим правилам: число объединяемых клеток 2, 4, 8, 16, 32 и т. д.; объединять надо как можно больше клеток, а самих объединений должно быть как можно меньше.
Так, для нашей функции получим:
х2 х2х1 -1270247651 1
х10 0
Это означает, что переменную х2 можно исключить, а значит f = х1.
ПР. Пусть дана функция 3-х переменных:
f=x1˄х2˄х3˅x1˄х2˄х3˅x1˄х2˄х3˅x1˄х2˄х3˅x1˄х2˄х3Тогда ее карта Карно имеет вид:
х2 х2 х2х2х1 -127041910-1270419101 1 1 1
х11 х3 х3х3х3
Прямоугольник, содержащий 4 единицы в 1-й строке, позволяет исключить переменные х2 и х3, а прямоугольник, содержащий две единицы в 1-м столбце, - переменную х1.
Т.о., f= х1 ˅ (х2 ˄ х3)
ПР. Пусть f=x1˄х2˄х3˄х4˅х1˄х2˄х3˄х4˅x1˄х2˄х3˄х4˅x1˄х2˄х3˄х4˅x1˄х2˄х3˄х4Составим для этой функции карту Карно:
х2 х2 х2х2х1 1 1 1 х3
х1 х3х1х3х11 1 х3
х4 х4х4х4 Четыре единицы по углам таблицы позволяют исключить х1 и х2, а две соседние единицы в 1-й строке – переменную х4.
Значит, f=(х3˄х4)˅x1˄х2˄х35.7. Канонический многочлен Жегалкина. Методика представления
булевой функции в виде многочлена Жегалкина
Кроме булевой алгебры существуют еще алгебра Жегалкина, которая оперирует булевыми функциями так же, как и булева алгебра, но строится всего лишь на основе 2-х операций:
- умножения (соответствует конъюнкции);
- сложения по модулю 2 (соответствует исключающей дизъюнкции).
Х1 Х2 Х1∙Х2 Х1+Х2
1 1 1 0
1 0 0 1
0 1 0 1
0 0 0 0
Свойства алгебры Жегалкина
1. Коммутативность обеих операций
Х1 ∙ Х2 = Х2 ∙ Х1 Х1 + Х2 = Х2 + Х1
2. Ассоциативность умножения и сложения
(Х1 ∙ Х2) ∙ Х3 = Х1 ∙ (Х2 ∙ Х3) (Х1 + Х2) + Х3 = Х1 + (Х2 + Х3)
3. Дистрибутивность умножения относительно сложения
Х1 ∙ (Х2 + Х3) = Х1 ∙ Х2 + Х1 ∙ Х3
(!!) Второй дистрибутивности нет.
4. Свойства констант: х ∙ 0 = 0 х ∙ 1 = х х + 0 = х
(!!) Свойства 1 – 4 полностью соответствуют свойствам алгебры чисел.
Особенными являются свойства 5 и 6.
5. Закон приведения подобных: х + х = 0
6. Закон поглощения для умножения: х ∙ х = х
Соотношения, устанавливающие связи обеих алгебр
1. х = 1 + х
2. х1 х2 = х1 ∙ х2
3. х1 х2 = х1 + х2 + х1 ∙ х2
4. х1 + х2 = х1 х2 х1 х2(!!) Последняя формула, по сути, есть закон отмены исключающей дизъюнкции.
Все эти формулы могут быть легко доказаны с помощью таблиц истинности.
Опр. Каноническим многочленом Жегалкина называется такой многочлен, члены которого не содержат числовых коэффициентов, отличных от 1, и линейны относительно любой из переменных (все переменные в 1-ой степени).
Любую булеву функцию можно единственным образом представить в виде многочлена Жегалкина.
Представление булевой функции в виде многочлена Жегалкина и обратный переход делаются с применением формул, выражающих свойства обеих алгебр, а также формул перехода.
ПР. Данные булевы функции запишем в виде многочлена Жегалкина:
х (х у) = х х х у = F x y = x y = x ∙ y
/2-ой способ: х (х у) = х ∙ ((1 + х) у) = х ∙ (1 + х + у + (1 + х) ∙ у) = х ∙ (1 + х + у + у + + х ∙ у) = х ∙ (1 + х + х ∙ у) = х + х ∙ х + х ∙ х ∙ у = х + х + х ∙ у = х ∙ у/
х → у = х у = (1 + х) у = 1 + х + у + (1 + х) ∙ у = 1 + х + х ∙ у
x ↔ y = (х у) (y x) = (1 + х + х ∙ у) ∙ (1 + y + х ∙ у) = 1 + y + х ∙ у + х + х ∙ y + x ∙ x ∙ y + x ∙ y + x∙ y ∙ y + x ∙ x ∙ y ∙ y = 1 + y + x + x ∙ y + x ∙ y + x ∙ y + x ∙ y = 1 + y + x
x (y z) = x + (y z) + x ∙ (y z) = x + y + z + y ∙ z + x ∙ (y + z + y ∙ z) = = x + y + z + y ∙ z + x ∙ y + x ∙ z + x ∙ y ∙ z
x / y = x y = x∙y = 1 + x ∙ y
x ↓ y = xy = x+y+x∙y = 1 + x + y + x ∙ y
ПР. Данный многочлен Жегалкина представим в виде булевой функции:
1 + x + y + x ∙ y = 1 + х у = x y/2-ой способ: 1 + x + y + x ∙ y =(1 + у) + х ∙ (1 + у) = (1 + у)∙ (1 + х) = у∙х = у х = x y/
1 + x + z + x ∙ z + x ∙ y + x∙ y ∙ z = (1 + z) + x ∙ (1 + z) + x ∙ y ∙ (1 + z) = (1 + z) ∙ (1 + x + x∙ y) = z (1 + x ∙ (1 + y)) = z (1 + x y) = z x y = z (x y)
5.8. Приложение логических функций к анализу и синтезу
релейно-контактных схем. Логические схемы
Контактная схема представляет собой устройство из проводов и контактов, связывающих несколько полюсов (входов, выходов).
Контакты бывают:
* замыкающие, которые в рабочем состоянии замыкают цепь:
1890395158115804545158115 х
* размыкающие, которые замыкают цепь в нерабочем состоянии:
18700751149350814070125730 хРабочему состоянию контакта (кнопка нажата) ставится в соответствие 1, нерабочему – 0, наличию тока в цепи – 1, отсутствию тока – 0.
При управляющем воздействии контакт меняет свое состояние, в зависимости от чего пропускает электрический ток или препятствует его прохождению. При этом следует иметь в виду, что ключи, обозначенные одинаковыми буквами, связаны между собой и управляются одной кнопкой.
Оказывается, что любую логическую формулу (булеву функцию) можно реализовать схемой, состоящей из последовательно и параллельно соединенных ключей (контактов).
Операции отрицания соответствует схема с одним размыкающим ключом:
1120140173355001524017335500 ХЕсли кнопка нажата (Х = 1), ключ разомкнут, тока в цепи нет, при отпущенной кнопке (Х = 0) ключ замкнут, и в цепи течет электрический ток.
Операции конъюнкции соответствует схема с 2-мя последовательно соединёнными замыкающими контактами:
11874510668000232029010096500120586510096500 х1 х2
Ток в цепи есть, если нажаты обе кнопки одновременно (Х1 = Х2 = 1).
Операции дизъюнкции соответствует схема с 2-мя параллельно соединёнными замыкающими контактами:
141414597790004616459779000112966598425004629159842500 х1
1415415130175002476513017500
11296651333500046291511430000 х2
Электрический ток в цепи есть, если нажата хотя бы одна из кнопок.
Построим контактные схемы для импликации и эквиваленции.
Т.к. справедлива равносильность Х1 → Х2 ≡ Х1 ∨ Х2, то импликации будет соответствовать следующая схема:
4616451009650014141451009650011296651041400046291510414000 х11415415130175002476513017500
11296651428750046291513335000 х2
Операции эквиваленции будут соответствовать две различные схемы, т.к. имеют место две равносильности:
Х1 ↔ Х2 ≡ (Х1 ∨ Х2) ∧ (Х2 ∨ Х1)
2947670147955001966595147955002596515150495001967865150495001566545147955006235701479550013201651504950063436515049500 х1 х29017014668500294894015875000156781515875000
2596515850900019678658509000132016585090006248408509000 х2 х1
Х1 ↔ Х2 ≡ (Х1 ∧ Х2) ∨ (Х1 ∧ Х2)
2595245120650006330951301750063436511874500132969012827000227266511874500 х1 х2
2349518097500259651519367500
22726651231900013296901231900063436512319000 х1 х2Последние две цепи равносильны: при одинаковых значениях Х1 и Х2 на входах значения на выходах равны.
Опр. Две контактные схемы называются равносильными, если эти схемы обладают одинаковыми функциями проводимости.
Из двух равносильных схем более простой считается та, которая содержит меньшее число контактов. Именно математическая логика позволяет решать проблему минимизации контактных схем (получение результата ценой минимального количества контактов).
ПР. Составить контактную схему следующей логической формулы:
У = ((Х1 ∧ Х2) ∧ ((Х1 ∧ Х2) ∨ (Х1 ∧ Х2))) ∨ (Х1 ∧ Х2 ∧ Х3)
367284017653000346329017653000279654017653000217741517653000217741517653000 х1 х2
7378701339850039668451339850036728401320800019678651320800013201651320800073914013208000 х1 х2
2349520828000396811522098000346329010668000279654010668000217741510668000 х1 х274866516002000335851516002000259651516002000179641516002000 х1 х2 х3
Заметим, что хотя в формуле 9 контактов, ими управляют 3 кнопки – для Х1, Х2 и Х3.
Упростим формулу:
(Х1 ∧ Х2 ∧ Х1 ∧ Х2) ∨ (Х1 ∧ Х2 ∧ Х1 ∧ Х2) ∨ (Х1 ∧ Х2 ∧ Х3) ≡ (F ∧ Х2) ∨ (F ∧ Х1) ∨ (Х1 ∧ Х2 ∧ Х3) ≡ F ∨ F ∨ (Х1 ∧ Х2 ∧ Х3) ≡ Х1 ∧ Х2 ∧ Х3
Соответственно упрощается контактная схема:
74866516002000335851516002000259651516002000179641516002000 х1 х2 х3
Недостатками контактных схем являлись их низкая надежность и быстродействие, большие размеры и потребление энергии. Поэтому попытка использовать такие схемы в ЭВМ не оправдала себя. Появление вакуумных и полупроводниковых приборов позволило создавать логические элементы с быстродействием от 1 миллиона переключений в секунду. Именно такие электронные схемы нашли свое применение в качестве элементной базы ЭВМ. Вся теория, изложенная для контактных схем, была перенесена на электронные схемы.
Логические (структурные или функциональные) схемы представляют собой соединение логических устройств.
Важнейшими из таких устройств являются триггеры, полусумматоры, сумматоры, шифраторы, дешифраторы, счетчики, регистры и др. В свою очередь, логические устройства можно рассматривать как цепи из логических элементов.
Опр. Логическим элементом называется дискретный преобразователь, который после обработки входных двоичных сигналов выдает на выходе сигнал, являющийся значением одной из логических операций.
Простейшим логическим элементом является инвертор, выполняющий функцию отрицания. Если на вход поступает сигнал, соответствующий 1, то на выходе будет 0. И наоборот. У этого элемента один вход и один выход. На функциональных схемах он обозначается:
3473454699000
675640117475006851651327150-97790109220х

Логический элемент, выполняющий логическое сложение, называется дизъюнктором. Он имеет, как минимум, два входа. На функциональных схемах он обозначается:
347345158751
001
х
-75565208915-700424991
6877056985у

Логический элемент, выполняющий логическое умножение, называется конъюнктором. Он имеет, как минимум, два входа. На функциональных схемах он обозначается:
34734513336&
00&
х
-88900236855-700424991
6965956985у
Другие логические элементы строятся из этих трех простейших. Даже для импликации и эквивалентности нет специальных логических элементов, т.к. А → В можно заменить на А В; А ↔ В можно заменить на (A B) (A B).
Сложной логической функции f(х, у) = х у соответствует схема:
1176020184150035153815697&
00&
х
159512017589500-700424991
16998951905082075973660у
-6985057150
Это: элемент «И-НЕ» Аналогично: элемент «ИЛИ-НЕ»
35235018371&
00&
х
83081617540800-700424991
8648702540у
-6985057150
352350156971
001
х
-700424991
828040336550086550573660у
-6985057150
Алгоритм построения логических схем
1) Определить число переменных
2) Определить количество логических операций и их порядок
3) Взять для каждой логической операции элемент
4) Объединить логические элементы в порядке выполнения логических операций
ПР. Составим логическую схему для функции f = A ˅ B ˄ A.
Имеем две переменные: А и В.
Две логические операции: 1 - , 2 - ˅.
Строим схему:

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

F = X ˄ Y ˅ X˄ Z
6. Логика предикатов
6.1. Основные понятия, связанные с предикатами
Пусть дано высказывание «7 – простое число». Оно утверждает, что число «7» (субъект высказывания) обладает свойством «быть простым числом». Очевидно, что это истинное высказывание.
Если в рассмотренном примере заменить конкретное число «7» переменной «х», то получится высказывательная форма «х – простое число». При одних значения «х» (например: 13, 17) эта форма дает истинные высказывания, а при других значениях (например: 6, 28) – ложные высказывания.
Опр. Предложения с переменными, которые становятся высказываниями в результате замены переменных их допустимыми значениями, называются предикатами.
Опр. Предикат с одной переменной называется одноместным (свойством), двух и более переменных – двуместным, трехместным и т.д. (отношением)
Обозначение: Р(х), Q(x, y), S(x, y, z), P(x1, x2,…, xn)
Напр.: 1) Р(х) = «х делится на 5» – одноместный предикат
2) «х2 – 2х = 0» – одноместный предикат
3) Q(x;y) = «Река х впадает в море у» – двуместный предикат
4) «x + y = z» – трехместный предикат
(!!) Очевидно, что если в предикате одну переменную заменить ее конкретным значением, то местность предиката уменьшается на 1. Так как одноместный предикат после подстановки вместо переменной конкретного значения превращается высказывание, то высказывание можно считать нульместным предикатом.
При задании предиката обязательно должно быть указано множество тех значений, которые могут принимать переменные. Его называют областью определения предиката и обозначают u. При этом, множество тех значений из u, при которых данный предикат является истинным высказыванием, называется областью истинности предиката и обозначается I.
Напр.: 1) Р(х) = «х – четное число»
UP = N, IP = хх=2к, где к∈N 2) Q(x) = «х2 – 2х = 0»
UQ = R, IQ = {0;2}
3) P(x, y) = «х кратно у»
UP = N2 (множество упорядоченных пар натуральных чисел)
IP = {(x; y) ∈ N2│x ⋮ y}
Опр. Предикат называется тождественно истинным, если он становится истинным высказыванием при любых допустимых значениях переменных, т.е. его множество истинности совпадает с областью определения.
Опр. Предикат называется тождественно ложным, если он становится ложным высказыванием при всех допустимых значениях переменных, т.е. его множество истинности является пустым.
Опр. Предикат, который не является тождественно истинным или тождественно ложным, называется выполнимым.
Напр.: 1) (х – у)(х + у) = х2 – у2 – тождественно истинный двуместный предикат на множестве R2
2) х + 1 = х – тождественно ложный одноместный предикат на множестве R
Опр. Два предиката называются эквивалентными (равносильными), если они определены на одном и том же множестве и их множества истинности совпадают.
Понятие равносильности играет важную роль при рассмотрении уравнений, поскольку каждое уравнение представляет собой некоторый предикат, а задача решения уравнения – задачу нахождения множества истинности соответствующего предиката. В процессе решения уравнения над ним производятся различные преобразования, при этом важно, чтобы получаемый предикат был равносилен исходному, т.е. область истинности не изменялась.
Приведем пример цепочки равносильных преобразований в случае уравнения: х2 = 9
х2 = 9 <=> х2 – 9 = 0 <=> (х – 3) (х + 3) = 0 <=> (х = 3) (х = – 3) => множество истинности исходного предиката есть множество 3; -36.2. Логические операции над предикатами
Т.к. предикат при каждом наборе переменных из его области определения обращается в высказывание, то над предикатами можно выполнять все те логические операции, которые изучались в алгебре высказываний. Правда, составление таблиц истинности здесь или невозможно (если область определения предиката является бесконечным множеством), или весьма громоздко. Поэтому рассмотрим интерпретацию логических операций над предикатами на языке множеств. Для простоты рассуждения рассмотрим одноместные предикаты.
I. Отрицание
Опр. Отрицанием предиката Р(х), определенного на множестве u, называется предикат Р(х), определенный на том же множестве, который становится истинным высказыванием только для тех значений х, при которых предикат Р(х) является ложным высказыванием и наоборот.
216789069405500(!!) Множеством истинности предиката Р(х) является дополнение множества истинности предиката Р(х) до множества u.
374903917145U
00U
253936511303000251206017843500
2806065118110IP
00IP

Умение строить отрицание предиката часто используется в математике. Так, например, решая задачу: Найти D(f), если f(x) = 1x2-2x-3 – мы, вместо того, чтобы решать неравенство х2 – 2х – 3 ≠ 0, решаем уравнение х2 – 2х – 3 = 0 и, получив в результате х = 3 и х = - 1, берем отрицание: х ≠3 и х ≠ - 1.
II. Конъюнкция
Опр. Конъюнкцией 2-х предикатов P(x) и Q(x) называется предикат P(x) Q(x), который становится истинным высказыванием лишь при тех значениях х, при которых оба предиката становятся истинными высказываниями.
2386965788670IP
00IP
225361566103500(!!) Очевидно, что множество истинности предиката P(x) Q(x) – есть пересечение множеств истинности исходных предикатов, т.е. IP ∩ IQ.
397764055880U
00U
3101340152400IQ
00IQ

3110865155575003110865222250310133928892600315849079375
313944184455003148965151130310134017780
Понятие конъюнкции предикатов тесно связано с понятиями систем уравнений и неравенств.
III. Дизъюнкция
Опр. Дизъюнкцией 2-х предикатов P(x) и Q(x) называется предикат P(x) Q(x), который становится ложным высказыванием лишь при тех значениях х, при которых оба предиката становятся ложными высказываниями.
(!!) Для дизъюнкции P(x) Q(x) множеством истинности является объединение множеств IP ∪ IQ.
2434590112395U
00U
22631403505202120265264795197739022669600183451525527000157734025527000172021532194500146304023622013296902457451186815331470001501140229235IQ
00IQ
996315229235IP
00IP
8439158636000
107251510287000
Понятие дизъюнкции предикатов тесно связано с уравнениями.
IV. Импликация
Опр. Импликацией 2-х предикатов P(x) и Q(x) называется предикат P(x) → Q(x), который становится ложным высказыванием лишь при тех значениях х, при которых Р(х) становятся истинным высказыванием, а Q(x) - ложным.
(!!) Область истинности предиката P(x) → Q(x) - есть множество U \ (IP \ IQ)
234886584455U
00U
1443990234315IQ
00IQ
948690272415IP
00IP
7391403429000
Если IP ⊂ IQ, то говорят, что Q(x) логически следует из Р(х). В этом случае множеством истинности предиката P(x) → Q(x) является все множество u.
V. Эквиваленция
Опр. Эквиваленцией 2-х предикатов P(x) и Q(x) называется предикат P(x) ↔ Q(x), который становится истинным высказыванием лишь при тех значениях х, при которых Р(х) и Q(x) становятся высказываниями с одинаковыми истинностными значениями.
(!!) Множество истинности предиката P(x) ↔ Q(x) можно описать формулой IP ∩ IQ ∪ IP∪IQ1053465107950IQ
00IQ
367665117475IP
00IP
253365146050019011902914660108204016764011391903200402628902914652438401676402724155334000193929035814026289033909018535642152640026289022479000262889100965
1986915253365195834053340197739010096510915653486151072515215265108203972391002438403390910026289023431524384072390196786531051510915652724140025336527241519869151581150011010901390650026289013906511010905715
1834515158115193929024765234316129540002533651771652533652476526289031051519107159144000174879022479000108204023431526289023431511391904381523431572390
ПР. Определим вид данных предикатов:
«sin2x + cos2x = 1» - тождественно истинный одноместный предикат
U = R I = R
«cos x = 0» - выполнимый одноместный предикат
U = R I = xx= π2+ πn,n∈Z «x2 + y2 = z2» - выполнимый трехместный предикат
U = R3 I = x;y;z x2+ y2= z2;x,y,z∈R«х + у = 2х» - выполнимый двуместный предикат
U =R2 I = x;yy= x ;x,y∈R6.3. Кванторные операции над предикатами
В алгебре предикатов применяются еще две логические операции, которые отсутствуют в алгебре высказываний. Это операции навешивания кванторов. В результате применения этих операций к предикатам могут получиться либо снова предикаты, либо высказывания.
Квантор общности
Пусть предикат Р(х) определен на множестве u. Утверждение «для любого х из u выполняется Р(х)» или «все х из u обладают свойством Р(х)» обозначают посредством символа ∀х Р(х). Символ операции ∀ называется квантором общности.
Очевидно, что ∀х Р(х) является высказыванием.
Напр.: Пусть Р(х) = «х – простое число» определен на множестве N, тогда высказывание ∀х Р(х) = ∀х(х – простое число) является ложным высказыванием («любое натуральное число является простым», «все натуральные числа простые»).
Опр. Переход от одноместного предиката Р(х) к высказыванию ∀х Р(х) называется операцией связывания предметной переменной х квантором общности.
При этом переменную х называют связанной. Переменную, не связанную квантором общности, называют свободной.
(!!) Высказывание ∀х Р(х) является истинным тогда и только тогда, когда Р(х) – тождественно истинный предикат.
Рассмотрим теперь двуместный предикат Р(х; у) = «х делится на у», определенный на множестве 2. Ясно, что ∀х Р(х;у) = «все числа делятся на у» - одноместный предикат от предметной переменной у.
При у = 3 ∀х (х ⋮3) – ложное высказывание
При у = 1 ∀х (х ⋮1) – истинное высказывание
Таким образом, предикат ∀х Р(х;у) – выполнимый предикат
Очевидно, что предикат ∀у Р(х;у) = «х делится на любое число» является тождественно ложным предикатом, а предложение ∀х ∀уР(х;у) = «любое натуральное число делится на все натуральные числа» - ложное высказывание.
Квантор существования
Пусть предикат Р(х) определен на множестве u. Утверждение «существует х из u, обладающий свойством Р(х)» обозначают посредством символа ∃х Р(х). Символ операции ∃ называется квантором существования.
Очевидно, что ∃х Р(х) является высказыванием.
Так, ∃ х (х – простое число) – истинное высказывание (существует простое натуральное число).
Опр. Переход от одноместного предиката Р(х) к высказыванию ∃х Р(х) называется операцией связывания предметной переменной х квантором существования.
(!!) Высказывание ∃х Р(х) является ложным тогда и только тогда, когда Р(х) – тождественно ложный предикат.
Пусть дан двуместный предикат Р(х; у) = «х делится на у», тогда ∃х Р(х;у) – одноместный тождественно истинный предикат от предметной переменной у («существует такое натуральное число, которое делится на у»), а ∃у Р(х;у) – одноместный тождественно истинный предикат от переменной х («существует натуральный делитель числа х»).
Очевидно, что ∃х ∃уР(х;у) - есть истинное высказывание («существуют два натуральных числа, из которых первое является делителем второго»).
(!!) В п-местном предикате Р(х1; х2; …; хп) некоторые предметные переменные могут быть связаны квантором общности, а некоторые – квантором существования. Местность такого предиката определяется числом свободных переменных.
Напр.: ∀x∃y P(x;y;z) – одноместный предикат от переменной z.
ПР. Пусть дан двуместный предикат Р(х; у) = « х >у», определенный на множестве R2. Тогда
∀хР(х;у) = «Все действительные числа больше у» – тождественно ложный предикат от у
∀уР(х;у) = «Все действительные числа меньше х» – тождественно ложный предикат от х
∃хР(х;у) = «Существует действительное число, большее у» – тождественно истинный предикат от у
∃уР(х;у) = «Найдется действительное число, меньшее х» – тождественно истинный предикат от х
∀х ∀уР(х;у) = «Каждое действительное число больше всех действительных чисел» – ложное высказывание
∀х ∃уР(х;у) = «Для каждого действительного числа найдется большее его действительное число» – истинное высказывание
∃х ∀уР(х;у) = «Существует действительное число, большее всех действительных чисел» – ложное высказывание
ПР. Определите истинность высказываний, найдя области истинности предикатов.
∀х(x2- 3х+2=0) – ложное высказывание
Рх = «x2- 3х+2=0» - выполнимый предикат (I = {1; 2})
∃x(x2- 3x+2 >0) - истинное высказывание
Рх = «x2- 3x+2 >0» - выполнимый предикат (I = (-∞;1) ∪(2;+∞))
∀x((x2 – 6x + 8 ≥0) (x2 – 6x + 8 <0)) - истинное высказывание
P1(x) – «x2 – 6x + 8 ≥0» (I = -∞;2 ∪ 4;+∞)
P2(x) – «x2 – 6x + 8 <0» (I = 2;4)
IPQ = R => P Q – тождественно истинный предикат
∃x(x2+ x+4 <0) - ложное высказывание
Рх – тождественно ложный предикат (I = ∅)
∃x(х∈2;5→(x2- 6x+8=0)) - истинное высказывание
Р1(х) – «х∈2;5» (I =2;5)
P2(x) – «x2 – 6x + 8 =0» (I =2;4)
Р1 → Р2 – выполнимый предикат
6.4. Понятие предикатной формулы.
Основные равносильности логики предикатов
Опр. 1) Элементарными формулами алгебры предикатов являются:
- любое высказывание (как переменное (Х, У,…), так и постоянное (T, F));
- любой п-местный предикат Р(х1, х2, …, хп), где х1, х2, …, хп – свободные переменные, не связанные кванторами.
2) Если Ф – формула, содержащая свободную переменную х, то ∀х Ф и ∃х Ф - формулы алгебры предикатов, причем переменная х в них является связанной.
3) Если Ф формула, то Ф тоже формула, при этом характер предметных переменных при переходе от формулы Ф к формуле Ф не меняется.
4) Если Ф1 и Ф2 – формулы, причем такие, что одна и та же предметная переменная не является в одной из них связанной, а в другой – свободной, то Ф1 Ф2, Ф1 Ф2, Ф1 → Ф2, Ф1 ↔ Ф2 – формулы алгебры предикатов. В этих формулах те переменные, которые в исходных формулах были свободны, являются свободными, а те, которые были связанными, являются связанными.
(!!) Очевидно, что все формулы алгебры высказываний являются формулами алгебры предикатов.
Иерархия логических операций остается та же, что и в алгебре высказываний, однако следует иметь в виду, что кванторы ∀ и ∃ связывают сильнее, чем другие логические связки.
Все равносильности, известные в алгебре высказываний, распространяются на алгебру предикатов. Кроме них в алгебре предикатов существуют равносильности, связанные с кванторами.
Рассмотрим наиболее важные из них. Для простоты рассуждений вновь будем рассматривать одноместные предикаты.
Если предикат определен на конечном множестве М = a1;a2;…;an, то
а) ∀х Р(х)  Р(а1) Р(а2) … Р(ап);
б) ∃х Рх  Р(а1) Р(а2) … Р(ап).
/ а) Пусть ∀х Рх=1, тогда Р(х) – тождественно истинный предикат, следовательно Р(а1) = Р(а2) = … = Р(ап) =1, но тогда Р(а1) Р(а2) … Р(ап) = 1.
Если же ∀х Рх=0, то найдётся хотя бы одно значение х = ак, что Р(ак) = 0, но тогда Р(а1) Р(а2) … Р(ап) = 0./
Таким образом, кванторы – другая форма записи конъюнкции и дизъюнкции.
(!!) Кванторная форма записи конъюнкции и дизъюнкции пригодна и в случае, когда область определения предиката – бесконечное множество.
Знак отрицания можно внести под знак квантора, изменив квантор на двойственный, т.е.:
а) ∀хР(х)  ∃хР(х);
б) ∃хР(х)  ∀хР(х).
/ а) Левая часть читается «неверно, что для любого х предикат Р(х) истинен», а правая- «существует х, для которого Р(х) – ложный предикат». Ясно, что эти два утверждения имеют один и тот же смысл./
(!!) Это правило справедливо для многокванторных предикатов.
Напр.: ∀x∃y∀zP ≡ ∃x∀y∃zPКвантор общности обладает распределительным свойством относительно конъюнкции, т.е.: ∀x(Px Q(x))  ∀х Р(х) ∀х Q(х) Квантор существования обладает распределительным свойством относительно дизъюнкции, т.е.: ∃x(Px Q(x))  ∃х Р(х) ∃х Q(х)Одноименные кванторы можно менять местами, т.е.:
а) ∀х ∀уР(х;у)  ∀у ∀хР(х;у);
б) ∃х ∃уР(х;у)  ∃у ∃хРх;у.(!!) Разноименные кванторы менять местами нельзя.

Задания для самостоятельного решения
1) Постройте таблицы истинности формул логики, определите, к какому из видов они относятся:
Ф(А, В) = А → В А В;
Ф(А, В) = А →(А→ В ) ;
Ф(X1, X2, X3) = X1 X2 X3 ↔ X3.
2) Докажите с помощью таблицы истинности равносильность:
А ↔ В ≡А В A В.
3) Упростите:
1) Х→ Y У;
2) А В → В А;
3) (X → Y) → ((Y → Z) → (X \/ Y → Z)).
4) Для булевой функции f (x, y, z) = x z → y x найдите СДНФ и СКНФ путем составления таблицы истинности.
5) С помощью равносильных преобразований запишите для данных булевых функций их совершенные нормальные формы:
1) f (x1; x2; x3) = (x1 x2) ( x1 x2 х3);
2) f (x; y) = у x→y.
6) Запишите функцию эквиваленции с помощью стрелки Пирса и штриха Шеффера.
7) Отобразите булевы функции на п-мерный куб:
1) f (x) = x; 2) f (x1; x2) = x1 → x2 ↔ x1.
8) Минимизировать нижеприведенные функции, представленные картами Карно.

9) Преобразуйте булеву функцию (x y) (y z) x z в многочлен Жегалкина.
10) Представьте многочлен Жегалкина 1 + y ∙ z + x ∙ y ∙ z в виде булевой функции.
11) Составьте контактную схему для логической формулы:
1) х (y z у х); 2) (x y) (y z) x z; 3) у x → у.
12) Упростите КС:
206692512192000110998010096400109918512192000276796412192000 x
27686001968490080200519621400
3119119-381000801369-381000206692516255900109982016255900 y
41846514477900451231014922400384302015366900311975514922400x у
8020056095900270446510096400169481510096400 x y13) Постройте логическую схему булевой функции
f(x; y; z) = x (y z).
14) Составьте логическую функцию по схеме:

15) Идентифицируйте следующие предложения:
«при а = –1 верно равенство а3 + 2 = 1»;
2) 25 = – 5»;
3) «х2 + у2 >0»;
4) «3х – 5 = 4х + 1»;
5) «n – кратно 5».
16) Установите истинность высказываний, найдя области истинности предикатов:
1) ∀х (x2+ х+1 <0); 2) ∃х х+5=2х-3.17) На множестве натуральных чисел заданы предикаты А(п) = «п делится на 3», В(п) = «п делится на 5», С(п) = «п делится на 15». Определите истинность высказываний, сформулировав каждое из них:
1) ∀n (С(n) → В(n)); 2) ∃n (А(n) C(n)); 3) ∀n (С(n) → А(n) В(n)).
18) Пусть предикат Р(х; у) определен на множестве N2 и означает «х больше у». Определите истинность высказываний, сформулировав каждое из них:
1)∃х∃уР(х;у); 2) ∀х∀уР(х;у);
3) ∃у∀хР(х;у); 4) ∀у∃хР(х;у).
19) На множестве А = 1;2;3;4;…;20 заданы предикаты Р(х) = «х – четное число», Q(х) = «х делится на 7» и S(х) = «х – составное число». Найдите области истинности предикатов Р, P S, Q S, P → S, S ↔ Q.
20) Найдите отрицания следующих формул:
1)∃х(Px Q(x)); 2) ∀x(Pх↔Q(х)); 3) ∃x∀y(Px;y Qx;y).

Контрольные вопросы
1) Что называется высказыванием?
2) Дайте понятие истинностных значений высказываний.
3) Какие два высказывания называются равносильными?
4) Какие два высказывания называются простыми, а какие - сложными?
5) Дайте определение отрицания высказывания.
6) Определите конъюнкцию 2-х высказываний?
7) Что называется дизъюнкцией 2-х высказываний?
8) Что такое дизъюнкция 2-х высказываний в исключающем смысле?
9) Что называется импликацией 2-х высказываний?
10) Что называется эквиваленцией 2-х высказываний?
11) Дайте понятия логической переменной и логической постоянной.
12) Дайте понятие логической формулы?
13) Что такое ранг формулы?
14) Какая формула называется тождественно истинной? Как еще по-другому ее называют?
15) Какая формула называется тождественно ложной? Как ее по-другому называют?
16) Что значит выполнимая формула?
17) Какие две формулы называются равносильными?
18) Сформулируйте свойство коммутативности конъюнкции (дизъюнкции).
19) Сформулируйте свойство ассоциативности конъюнкции (дизъюнкции).
20) Перечислите свойства логических констант.
21) Чему равно отрицание конъюнкции (дизъюнкции) высказываний?
22) Сформулируйте закон исключенного третьего.
23) Сформулируйте закон противоречия.
24) В чем состоит закон двойного отрицания?
25) Дайте понятие теоремы.
26) Какая теорема называется обратной (противоположной, обратной противоположной)? Какая связь существует между ними?
27) Дайте определение логической функции.
28) Сколько существует булевых функций п переменных?
29) Какой формулой задается функция Шеффера? Пирса?
30) Дайте понятия конъюнктивной и дизъюнктивной нормальных форм.
31) При каком условии нормальные формы называют совершенными?
32) Сформулируйте алгоритмы представления булевой функции, заданной таблицей истинности, в СДНФ и СКНФ.
33) Какие две операции лежат в основе алгебры Жегалкина?
34) Что представляет собой закон приведения подобных в алгебре Жегалкина?
35) Дайте понятие многочлена Жегалкина.
36) Какая контактная схема соответствует операции конъюнкции? Дизъюнкции?
37) Что такое предикат и его местность?
38) Что называется областью определения и областью истинности предиката?
39) Какой предикат называется тождественно истинным? тождественно ложным? выполнимым?
40) Что представляет собой область истинности отрицания предиката?
41) Как найти область истинности конъюнкции (дизъюнкции, импликации, эквиваленции) предикатов?
42) Какие кванторные операции над предикатами известны?
43) Как меняется местность предиката при связывании переменной квантором?
44) Дайте понятие предикатной формулы.
Тест для самоконтроля
Задание № 1. (выберите один вариант ответа) Конъюнкция двух высказываний истинна тогда и только тогда, когда…
Варианты ответов:
хотя бы одно из высказываний истинно
оба высказывания истинны
одно из высказываний истинно, а другое ложно
оба высказывания ложны
Задание № 2. (выберите один вариант ответа) Логическая формула, которая является дизъюнкцией конъюнкций переменных или их отрицаний называется…
Варианты ответов:
1) совершенной дизъюнктивной нормальной формой
2) дизъюнктивной нормальной формой
3) совершенной конъюнктивной нормальной формой
4) конъюнктивной нормальной формой
Задание № 3. (выберите один вариант ответа) Чему равен ранг формулы
Ф = (А В) (A В)?
Варианты ответов:
4 2) 6 3) 5
Задание № 4. (выберите варианты ответов согласно тексту задания) Если скобки отсутствуют, то логические операции выполняются в следующей очерёдности…
Варианты ответов:
конъюнкция 2) импликация 3) отрицание 4) дизъюнкция
Задание № 5. (выберите один вариант ответа) Формула алгебры логики Ф(X, Y) = X Y → X является…
Варианты ответов:
тождественно истинной 2) тождественно ложной 3) выполнимой
Задание № 6. (выберите два варианта ответов) Допущена ошибка в следующей равносильности…
Варианты ответов:
А В ≡А В 2) А (А В) ≡ В
3) А А ≡ Т 4) А ↔ В ≡ (А В) (А ˅ В)
Задание № 7. (выберите один вариант ответа) Формула Ф = А→В имеет следующую таблицу истинности…
Варианты ответов:
1) 2) 3) 4)
А В Ф А В Ф А В Ф А В Ф
1 1 1 1 1 1 1 1 0 1 1 0
1 0 0 1 0 0 1 0 1 1 0 1
0 1 1 0 1 0 0 1 0 0 1 1
0 0 1 0 0 1 0 0 0 0 0 0
Задание № 8. (выберите один вариант ответа) Отрицание дизъюнкции двух высказываний равно…
Варианты ответов:
1) дизъюнкции отрицаний этих высказываний
2) конъюнкции этих высказываний
3) дизъюнкции этих высказываний
4) конъюнкции отрицаний этих высказываний
Задание № 9. (выберите один вариант ответа) Предложение «х – четное число» является …
Варианты ответов:
1) высказыванием
2) одноместным тождественно ложным предикатом
3) одноместным тождественно истинным предикатом
4) одноместным выполнимым предикатом
Задание № 10. (выберите один вариант ответа) Предикатом является следующее предложение…
Варианты ответов:
1) «число 13 – составное число» 2) «любое целое число кратно двум»
3) «х2 + 2х – 3 ≥ 0» 4) «х + у»
Задание № 11. (выберите несколько вариантов ответов) Одноместным тождественно ложным предикатом является предложение…
Варианты ответов:
1) «x2<0» 2) «число х кратно двум»
3) «∀х (х>у)» 4) «х + 1 = х»
Задание № 12. (выберите один вариант ответа) Предложение «∃х (х2≤0)» является…
Варианты ответов:
1) ложным высказыванием
2) истинным высказыванием
3) тождественно ложным одноместным предикатом
4) выполнимым одноместным предикатом
Задание № 13. (выберите два варианта ответов) Предикат Р(х;у) определен на множестве N2 и означает «х ≥у». Укажите истинные высказывания.
Варианты ответов:
1) ∃у∀хР(х;у) 2) ∀х∃уР(х;у) 3) ∃у∃хР(х;у) 4) ∀х∀уР(х;у)
Задание № 14. (выберите один вариант ответа) Ложным высказыванием является следующее предложение…
Варианты ответов:
1) «х - 2 = 3х + 4» 2) «х2 - 3х + 2»
3) «число 17 – простое число»4) «⩝ х (х ⋮ 2)»
Задание № 15. (выберите один вариант ответа) Найдите отрицание формулы ∃х(Px Q(x)).
Варианты ответов:
1) ∃х(Px Q(x)) 2) ∀х(Px Q(x))
3) ∀х(P(x) Q(x)) 4) ∀х(Px Q(x))Задание № 16. (выберите два варианта ответов) Допущена ошибка в следующей равносильности…
Варианты ответов:
1) ∀x(Px Q(x)) ≡ ∀х Р(х) ∀х Q(х)
2) ∃x(Px Q(x)) ≡ ∃х Р(х) ∃х Q(х)3) ∃x(Px Q(x)) ≡ ∃х Р(х) ∃х Q(х)
4) ∀x(Px Q(x)) ≡ ∀х Р(х) ∀х Q(х)Ответы на тест:
№1 – 2; №2 – 2; №3 – 3; №4 – 3142; №5 – 1; №6 – 2,4; №7 – 3; №8 – 4; №9 – 4; №10 – 3; №11 – 1,3,4; №12 – 2; №13 – 2,3; №14 – 4; №15 – 3; №16 – 1,3.

Приложенные файлы

  • docx file5.doc
    Размер файла: 444 kB Загрузок: 3