Элементы математической логики

Двум переменным соответствуют 4 различных варианта наборов значений: (1;1), (0;0), (1;0), (0;1). Пусть функции , , определяются таблицей.

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

Функция принимает значение 0 только в том случае, когда обе переменные принимают значение 0, поэтому: = .

Функция соответствует операции «импликация», т. е.: =.

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

3.3 Приведение функции к совершенной ДНФ

I. Элементарной конъюнкцией переменных называется конъюнкция переменных или их отрицаний.

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

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

записаны в виде ДНФ.

Применяя законы логики, любую булеву функцию можно привести к ДНФ. Это делается следующим образом. Прежде всего, удаляются знаки «>» и «-». Знак «>» удаляется с помощью закона . Для удаления знака «-» сначала применяется закон ; далее опять используется закон .

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

Пример. Привести функцию f(x; y; z) = к ДНФ.

Решение:

f(x; y; z) =

.

Функция f(x; y; z) уже записана в виде ДНФ. Но её можно упростить:

f(x; y; z) = .

Таким образом, для любой функции можно получить её ДНФ, причём не единственную.

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

1) каждое логическое слагаемое формулы, определяющей ДНФ, содержит все переменные, входящие в данную функцию;

2) все логические слагаемые формулы, определяющей ДНФ, различны;

3) ни одно логическое слагаемое формулы, определяющей ДНФ, не содержит одновременно переменную и её отрицание;

4) ни одно логическое слагаемое формулы, определяющей ДНФ, не содержит одну и ту же переменную дважды.

Такая ДНФ функции называется совершенной дизъюнктивной нормальной формой (СДНФ).

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

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

1) путём равносильных преобразований формулы А получают одну из ДНФ функции;

2) если в полученной ДНФ входящая в неё элементарная конъюнкция В не содержит переменную , то, используя равносильность , элементарную конъюнкцию В заменяем на две элементарные конъюнкции и , каждая из которых содержит переменную ;

3) если в ДНФ входят две одинаковые элементарные конъюнкции В, то лишнюю можно отбросить, пользуясь равносильностью ;

4) если некоторая элементарная конъюнкция В, входящая в ДНФ, содержит переменную и её отрицание , то В ? 0, и В можно исключить из ДНФ, как нулевой член дизъюнкции;

5) если некоторая элементарная конъюнкция, входящая в ДНФ, содержит переменную дважды, то одну переменную можно отбросить, пользуясь равносильностью ?.

После выполнения описанной процедуры будет получена СДНФ для данной функции.

Пример. Найти СДНФ для функции f(x; y; z) =.

Решение:

1) ищем ДНФ для данной функции:

f(x; y; z) =;

2) конъюнкция xxy содержит переменную x дважды, поэтому используем равносильность xx ? x:

f(x; y; z) = ;

3) элементарные конъюнкции и С ? xy не содержат переменной z, а элементарная конъюнкция не содержит переменной y, поэтому используем равносильности , , :

f(x; y; z) =;

4) теперь ДНФ содержит две одинаковые элементарные конъюнкции и две одинаковые элементарные конъюнкции , поэтому лишние отбрасываем, используя равносильности ?, ?:

f(x; y; z) =.

Таким образом, функция f(x; y; z) записана в виде ДНФ.

III. Если булева функция задана таблицей истинности, то из этой таблицы может быть получена формула, соответствующая данной функции (см. § 2). Следует отметить, что формула, получающаяся в этом случае по указанному в § 2 правилу, есть СДНФ для данной функции. Это ещё один способ приведения функции к СДНФ. Если булева функция задана формулой, то можно составить по ней таблицу истинности и по правилу, указанному в § 2, записать уже другую формулу, являющуюся СДНФ для данной функции.

Пример. Дана функция f(x; y; z) =. Записать её в виде СДНФ путём составления таблицы истинности.

Решение: составляем таблицу истинности:

х	y	z	yz	xy	yz>xy	f(x; y; z)
1	1	1	1	1	1	1
1	1	0	0	1	1	1
1	0	1	0	0	1	1
1	0	0	0	0	1	1
0	1	1	1	0	0	0
0	1	0	0	0	1	0
0	0	1	0	0	1	0
0	0	0	0	0	1	0

Тогда СДНФ для данной функции будет выглядеть так:

f(x; y; z) = .

3.4 Приведение функции к совершенной КНФ

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

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

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

Для СКНФ выполняются требования:

1) формула не является тождественно-ложной;

2) формула приведена к одному из видов КНФ;

3) из формулы удалены одинаковые элементарные дизъюнкции, кроме одной;

4) каждая элементарная дизъюнкция в КНФ включает все логические переменные, входящие в эту формулу.

Пример. Дана функция f(x; y; z) =. Записать её в виде КДНФ.

f(x; y; z) ===

== .

Полученная КНФ является совершенной.

3.5 Минимизация булевой функции. Метод карт Карно

Карты Карно являются одним из наиболее удобных способов минимизации (для n6).

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

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

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

Необходимо стремиться к тому, чтобы контуры содержали как можно больше ячеек.

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

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

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

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

Логическая функция F на карте Карно представляется совокупностью клеток, заполненных «1» или «0», если известны её значения при всём наборе аргументов, т.е. известна таблица истинности или СДНФ.

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

Для построения минимальной ДНФ производится «склеивание» единиц. Склеиваются только соседние клетки, которые отличаются значением одной переменной.

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

Алгоритм «склеивания» с помощью карт Карно :

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

2) Нанести единицы на карту Карно;

3) Объединить соседние единицы контурами, охватывающими

клеток, где m=0,1,2,3. При этом может оказаться, что единица попадает одновременно в два контура. Если контур охватывает более одной пары единиц одновременно, то предпочтительнее его не дробить на пары, а рассматривать как единый целый контур, например квадрат.

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

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

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

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

3.6 Двоичное сложение. Полином Жегалкина

Операция конъюнкция (называемая двоичным умножением) совпадает с арифметической операцией умножения над числами 0, 1, т. е.:

Обычное арифметическое сложение выводит за пределы множества {0;1}. Поэтому рассматривают операцию, называемую двоичным сложением и обозначаемую символом «+», которая определяется следующей таблицей истинности:

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

Для двоичного сложения имеют место все основные арифметические законы:

1) коммутативность: x + y ? y + x;

2) ассоциативность: (x + y) + z ? x + (y + z);

3) дистрибутивность умножения относительно сложения:

x(y + z) ? xy + xz.

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

Из определения операции двоичного сложения (см. таблицу 8) следует, что x + y ? 0 при x ? y, т.е. x + x ? 0. Имеет место и равносильность x + 0 ? x. В этом можно убедиться, составив соответствующую таблицу истинности.

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

1) операция отрицания: ? x + 1;

для доказательства достаточно составить таблицу истинности (таблица 9); из неё видно, что при одинаковых значениях х формулы и x + 1 принимают одинаковые значения;

2) дизъюнкция:

3) импликация:



5) двойная импликация:

,

т. к. xy + xy ? 0 (в силу равносильности х + х ? 0), х + 0 ? х.

Таким образом, имеют место равносильности:

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

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

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

Например, x(y + yz), xy + xyz - полиномы Жегалкина.

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

Пример 1. Представить функцию в виде полинома Жегалкина.

Решение:

Пример 2. Представить функцию в виде полинома Жегалкина.

Решение:

Примеры решения задач рассмотрены на третьем и четвертом обзорных установочных занятиях.

Пример 1:

Задать формулой функцию f (;;) , имеющую таблицу истинности:

Таблица истинности
			f(;;)
1	1	1	1
1	1	0	1
1	0	1	1
1	0	0	0
0	1	1	0
0	1	0	1
0	0	1	0
0	0	0	1

Решение: для наборов значений переменных (1;1;0), (1;0;1), (0;1;0), (0;0;0), на которых функция принимает значение 1, запишем конъюнкции , а искомая формула имеет вид:



f (;;)=.

Пример 2:

Найти формулу, определяющую функцию f(x; y; z), по заданной таблице истинности. Упростить полученную формулу.

Таблица истинности
х	y	z	f(х; y; z)
1	1	1	1
1	1	0	0
1	0	1	0
1	0	0	0
0	1	1	1
0	1	0	1
0	0	1	1
0	0	0	1

Решение: используя правило получения формулы из таблицы истинности для функции f(x; y; z), имеем: f(x; y; z) =.

Упрощаем полученную формулу, используя формулы логики:

f(x; y; z) =

.

Таким образом, f(x; y; z) = .

Пример 3. Привести функцию f(x; y; z) = к ДНФ.

Решение:

f(x; y; z) =

.

Функция f(x; y; z) уже записана в виде ДНФ. Но её можно упростить:

f(x; y; z) = .

Пример 4. Найти СДНФ для функции f(x; y; z) =.

Решение:

1) ищем ДНФ для данной функции:

f(x; y; z) =;

2) конъюнкция xxy содержит переменную x дважды, поэтому используем равносильность xx ? x:

f(x; y; z) = ;

3) элементарные конъюнкции и С ? xy не содержат переменной z, а элементарная конъюнкция не содержит переменной y, поэтому используем равносильности , , :

f(x; y; z) =;

4) теперь ДНФ содержит две одинаковые элементарные конъюнкции и две одинаковые элементарные конъюнкции , поэтому лишние отбрасываем, используя равносильности ?, ?:

f(x; y; z) =.

Таким образом, функция f(x; y; z) записана в виде ДНФ.

Пример 5. Дана функция f(x; y; z) =. Записать её в виде СДНФ путём составления таблицы истинности.

Решение: составляем таблицу истинности:

х	y	z	yz	xy	yz>xy	f(x; y; z)
1	1	1	1	1	1	1
1	1	0	0	1	1	1
1	0	1	0	0	1	1
1	0	0	0	0	1	1
0	1	1	1	0	0	0
0	1	0	0	0	1	0
0	0	1	0	0	1	0
0	0	0	0	0	1	0



Тогда СДНФ для данной функции будет выглядеть так:

f(x; y; z) = .

Пример 6. Метод Карно.

Покажем карты Карно для функций от двух, трех и четырех переменных:

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

Минимизируем функцию с помощью карты.



Получим ДНФ:

Пример 7. Представить функцию в виде полинома Жегалкина.

Решение:

Пример 8. Представить функцию в виде полинома Жегалкина.

Решение:

После изучения теории и решения примеров по данной теме можно решить задание №4 и №5 контрольной работы.



4. Логика предикатов

Изучить по учебной литературе вопросы:

· Предикаты. Основные понятия.

· Следование одного предиката из другого. Равносильность предикатов. Равносильные преобразования.

· Логические операции над одноместными предикатами.

· Кванторные операции над одноместными и двуместными предикатами.

· Построения отрицаний к предикатам, содержащим кванторы.

· Запись математических утверждений с помощью логики предикатов.

4.1 Предикаты. Основные понятия

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

Пример: «» - предикат, т. к. при подстановке x=1, y=0 предложение «» становится истинным высказыванием, а при подстановке, - ложным высказыванием. 49

«Он пошёл в кино» - предикат, в котором переменная - «он».

- предикат. Это предложение становится истинным высказыванием при подстановке любого вещественного числа x.

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

В предикат можно подставлять вместо переменных не все значения, а лишь взятые из какого-либо множества. Множество всех таких значений называется областью определения предиката. «Он пошёл в кино». Область определения: ученик, житель, но не число 2.

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

Одноместный предикат (имеющий одну переменную) определяет отношение принадлежности некоторому множеству. Принято одноместный предикат называть предикатом-свойством, n- местный (имеющий n переменных, для n>1) - предикатом-отношением, 0- местный предикат - высказыванием.

Полный прообраз (1) при Р называют множеством истинности Т(Р) предиката Р.

4.2 Следование одного предиката из другого. Равносильность предикатов. Равносильные преобразования

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

Тогда Т()Т()

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



Т()=Т()

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

Пример.

т.е. множество истинности каждого из этих уравнений состоит из одного числа 3.

4.3 Логические операции над одноместными предикатами

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

Это свойство автоматически выделяет из области определения два случая.

Тождественно-истинным называется предикат, истинный всюду на области определения. Т(Р)=D(P)

Тождественно-ложным называется предикат, множество истинности которого пусто: Т(Р)=Ш

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

- отрицание

- конъюнкция

- дизъюнкция

- импликация

- двойная импликация

4.4 Кванторные операции над одноместными и двуместными предикатами

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

Однако существует и другой способ. Рассмотрим предложение: «Для всех вещественных выполнено < 1». Оно является высказыванием, причём ложным. Т.е. несмотря на то, что в этом предложении есть переменная, оно является высказыванием, а не предикатом.

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

Существует два основных выражения, «связывающие переменную»:

1) - для всех значений, для любых значений…

2) - существует значение, найдётся, для некоторого…

< 1 «существует х, такой, что < 1» - это истинное высказывание (например х=0).

Эти выражения (и ) называются кванторами.

- квантор всеобщности

- квантор существования

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

[0;1] ? 1 - истинное высказывание, отрезок [0;1] - область определения.

Рассмотрим предикат Р(х,у) с двумя переменными, состоящий в том, что . Чем является предложение ? Подставим у=0. Получаем - это высказывание, причём ложное. Подставим у=1. Получим - тоже ложное высказывание.

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

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

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

Ясно, что каждую из n переменных можно связать двумя возможными кванторами, поэтому только за счёт выбора кванторов имеем уже вариантов получения высказывания из предиката. А ведь важен ещё и порядок «связывания» переменных.

Обратимся вновь к предикату Р(х,у). Рассмотрим предикат:

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

Такой у существует! Это, например,

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

Рассмотрим теперь предикат

Свяжем переменную у квантором существования. Получаем высказывание: Установим истинностное значение этого высказывания.

Если это высказывание истинно, то при каком-то значении у (обозначим его ) истинно высказывание

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

Итак, при перестановке порядка разноименных кванторов истинностное значение высказывания может меняться!

52

Особенно хорошо это видно на примере обыденного языка. Рассмотрим, например, высказывание: «В нашем кафе каждый столик обслуживается официантом».

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

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



4.5 Построения отрицаний к предикатам, содержащим кванторы

Правило отрицания высказываний с кванторами:

=

=

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

Правило отрицания работает и в случае нескольких переменных «снабжённых» кванторами.

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

Это правило следует из правила отрицания для одного квантора.

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

Тогда = согласно правилу отрицания с одним квантором. Теперь ещё раз применяем правило отрицания с одним квантором для внутреннего предиката и окончательно получаем:

=

Пример. Построим отрицание высказывания:

>>[0;1] [0;1] ||<||<

Меняем все кванторы на противоположные в соответствии с правилом отрицания:

>>[0;1]: [0;1]:

В соответствии со свойствами логических операций окончательно имеем:

>>[0;1]: [0;1]:(||<д) (| |??)

4.6 Запись математических утверждений с помощью логики предикатов

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

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

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

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

Пример. Определение предела последовательности "Число а называется пределом последовательности , если для всякого положительного числа существует такое натуральное число , что для всякого натурального , большего " на языке логики предикатов записывается так:

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

Примеры решения задач рассмотрены на пятом обзорном установочном занятии.

Пример 1. Среди следующих предложений выделить предикаты и для каждого из них указать область истинности, если область определения D = R для одноместных предикатов и D = RЧR для двухместных предикатов:

1. х + 5 = 1

2. при х = 2 выполняется равенство х2 - 1 = 0

3. х2 - 2х + 1 = 0

4. существует такое число х, что х3 - 2х + 1 = 0

5. х + 2 < Зх - 4

6. однозначное неотрицательное число х кратно 3

7. (х + 2) - (3х - 4)

8. х2 + у2 > 0

Решение. 1) Предложение является одноместным предикатом

Р(х) = {- 4}; 2) предложение не является предикатом. Это ложное высказывание; 3) предложение является одноместным предикатом Р(х) = {1}; 4) предложение не является предикатом. Это истинное высказывание; 5) предложение является одноместным предикатом Р(х) = (3; +?); 6) предложение является одноместным предикатом Р(х) = {0; 3; 6; 9}; 7) предложение не является предикатом; 8) предложение является двухместным предикатом Q(х,y) = RЧR \ {(0,0)}.

Пример 2.

Определить множество истинности предикатов, заданных на соответствующих множествах:

1. Р: «х кратно 3», Область определения: D={1,3,5, 6, 9};

2. Q: «sin2x + cos2x = 1» .

Решение.

1. Т(Р)= {3, 6, 9}; 2. Т(Q) = R - множество вещественных чисел.

Пример 3.

На множестве М= {3,4,5,6,7,8} заданы предикаты P(x) : «х - простое число», Q(x): «х - нечетное число». Составить таблицы истинности. Равносильны ли предикаты на множестве а) М; б) L = {2,3,4,5,6,7,8}; в) К = {3,4,5,6,7,8,9}?

Составим таблицы истинности предикатов на данных множествах:

М	Р(х)	Q(x)	L	Р(х)	Q(x)	K	Р(х)	Q(x)
3	1	1	2	1	0	3	1	1
4	0	0	3	1	1	4	0	0
5	1	1	4	0	0	5	1	1
6	0	0	5	1	1	6	0	0
7	1	1	6	0	0	7	1	1
8	0	0	7	1	1	8	0	0
			8	0	0	9	0	1

На множестве М Т(Р) = Т(Q), следовательно на этом множестве предикаты равносильны. На множествах L и К условие равносильности не соблюдается.

Пример 4. Р(х): «х² 0», Q(x): «2^|x| = cosx».

Область истинности предиката Р(х) : х =0, область истинности предиката Q(x) : х = 0.

Значит, Т(Р) = Т(Q) и предикаты равносильны.

После изучения теории и решения примеров по данной теме можно решить задание №6 и №7 контрольной работы.

Варианты контрольной работы находятся в Приложении 1.

Итоговая аттестация проходит в форме дифференцированного зачёта. Вопросы к зачёту находятся в Приложении 2.



Список литературы

1. А.В. Фёдорова «Основы теории множеств» (методическое пособие). СПб, СПИШЭ, 2007

2. А.В. Фёдорова «Элементы математической логики» (методическое пособие). СПб, СПбКИУ, 2008 г

3. А.В. Фёдорова «Элементы математической логики: булевы функции» (методическое пособие). СПб, СПбКИУ, 2008 г

4. М.С. Спирина, П. А. Спирин «Дискретная математика». Москва, «Академия», 3-е изд., 2018 г

5. И.В. Романовский «Дискретный анализ», СПб, «Невский диалект», 2010.

Интернет-ресурсы:

1. www.bestreferat.ru/referat-201452.html

2. vmg.pp.ua/books/Математика



Приложение 1

1. Контрольная работа выполняется в отдельной тетради в клетку, на обложке (зеленой) которой должны быть ясно написаны: Элементы математической логики, фамилия студента, его имя, группа з22928/1, электронный адрес студента; на титульном листе (первой страничке в клеточку) должны быть ясно написаны: Контрольная работа №1 по теме «Логика высказываний. Булевы функции. Логика предикатов», фамилия студента, его имя, группа з228/1 и № варианта.

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

3. На каждой странице тетради необходимо оставлять поля шириной 3-4 см для замечаний преподавателя.

4. Контрольная работа выполняется самостоятельно.

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

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

I вариант

1. Даны множества:

Найти: AZ; B?N; DZ. Указать все подмножества множества B.

2. Определить значение истинности высказывания

где: P: «Для любого вещественного х выполняется неравенство »;

Q: «Москва - столица России».

3. Упростить формулу:

4. Представить булеву функцию в виде СДНФ с помощью равносильных преобразований:

5. Дана функция:

1) задать эту функцию таблично; 2) найти минимальную ДНФ функции методом карт Карно.

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

P(x): «», Q(x): «», если:

R; б).

7. Найти множество истинности предиката, если R:

II вариант

1. Даны множества:

Найти: множество полином предикат логический

D?N, E \ Z; A?N.

Указать все подмножества множества E.

2. Определить значение истинности высказывания

,

где: P: «Существует наибольшее целое отрицательное число»;

Q: «Лондон - столица Великобритании».

3. Упростить формулу:

4. Представить булеву функцию в виде СДНФ с помощью равносильных преобразований:

5. Дана функция:

1) задать эту функцию таблично; 2) найти минимальную ДНФ функции методом карт Карно.

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

P(x): «», Q(x): «», если:

R; б).

7. Найти множество истинности предиката, если R:

III вариант

1. Даны множества:

Найти:

D?N, E \ Z; A?N.

Указать все подмножества множества E.

2. Определить значение истинности высказывания

где: P: «Париж - столица Франции»;

Q: «Существует вещественное x, такое, что <0».

3. Упростить формулу:

4. Представить булеву функцию в виде СДНФ с помощью равносильных преобразований:



5. Дана функция:

1) задать эту функцию таблично; 2) найти минимальную ДНФ функции методом карт Карно.

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

P(x): «», Q(x): «», если:

R; б).

7. Найти множество истинности предиката, если R:

IV вариант

1. Даны множества:

Найти:

AZ; B?N; DZ.

Указать все подмножества множества B.

2. Определить значение истинности высказывания

,

где: P: «Берлин - столица Германии»;

Q: «Для любого вещественного х выполняется неравенство ».



3. Упростить формулу:

4. Представить булеву функцию в виде СДНФ с помощью равносильных преобразований:

5. Дана функция:

1) задать эту функцию таблично; 2) найти минимальную ДНФ функции методом карт Карно.

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

P(x): «», Q(x): «», если:

R; б).

7. Найти множество истинности предиката, если R:

V вариант

1. Даны множества:

Найти:

AZ; B?N; DZ.

Указать все подмножества множества B.

2. Определить значение истинности высказывания

,

где: P: «Осло - столица Норвегии»;

Q: «Существует вещественное число, квадрат которого не является положительным».

3. Упростить формулу:

4. Представить булеву функцию в виде СДНФ с помощью равносильных преобразований:

5. Дана функция:

1) задать эту функцию таблично; 2) найти минимальную ДНФ функции методом карт Карно.

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

P(x): «», Q(x): «», если:

R; б).

7. Найти множество истинности предиката, если R:

VI вариант

1. Даны множества:

Найти:

D?N, E \ Z; A?N.

Указать все подмножества множества E.

2. Определить значение истинности высказывания

где: P: «Квадрат гипотенузы равен сумме квадратов катетов, для прямоугольного треугольника»;

Q: «Хельсинки - столица Финляндии».

3. Упростить формулу:

4. Представить булеву функцию в виде СДНФ с помощью равносильных преобразований:

5. Дана функция:

1) задать эту функцию таблично; 2) найти минимальную ДНФ функции методом карт Карно.

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

P(x): «», Q(x): «», если:

R; б).

7. Найти множество истинности предиката, если R:

VII вариант

1. Даны множества:

Найти:

AZ; B?N; DZ.

Указать все подмножества множества B.

2. Определить значение истинности высказывания

где: P: «Существует вещественное х, такое, что »;

Q: «Санкт-Петербург - столица России».

3. Упростить формулу:

4. Представить булеву функцию в виде СДНФ с помощью равносильных преобразований:

5. Дана функция:

1) задать эту функцию таблично; 2) найти минимальную ДНФ функции методом карт Карно.

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

P(x): «», Q(x): «», если:

R; б).

7. Найти множество истинности предиката, если R:

VIII вариант

1. Даны множества:

Найти:

D?N, E \ Z; A?N.

Указать все подмножества множества E.

2. Определить значение истинности высказывания

,

где: P: «Существует наибольшее целое число»;

Q: « Прага - столица Чехословакии».

3. Упростить формулу:

4. Представить булеву функцию в виде СДНФ с помощью равносильных преобразований:

5. Дана функция:

1) задать эту функцию таблично;

2) найти минимальную ДНФ функции методом карт Карно.

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

P(x): «», Q(x): «», если:

R; б).

7. Найти множество истинности предиката, если R:

IX вариант

1. Даны множества:

Найти:

AZ; B?N; DZ.

Указать все подмножества множества B.

2. Определить значение истинности высказывания

где: P: «Сумма углов любого треугольника равна 180 градусов»;

Q: «Париж - столица Германии».

3. Упростить формулу:

4. Представить булеву функцию в виде СДНФ с помощью равносильных преобразований:

5. Дана функция:

1) задать эту функцию таблично; 2) найти минимальную ДНФ функции методом карт Карно.

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

P(x): «», Q(x): «», если:

R; б).

7. Найти множество истинности предиката, если R:

X вариант

1. Даны множества:

Найти:

D?N, E \ Z; A?N.

Указать все подмножества множества E.

2. Определить значение истинности высказывания

,

где: P: «Пекин - столица Китая»;

Q: «Для любого вещественного х выполняется: ».

3. Упростить формулу:

4. Представить булеву функцию в виде СДНФ с помощью равносильных преобразований:

5. Дана функция:

1) задать эту функцию таблично; 2) найти минимальную ДНФ функции методом карт Карно.

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

P(x): «», Q(x): «», если:

R; б).

7. Найти множество истинности предиката, если R:

XI вариант

1. Даны множества:

Найти:

AZ; B?N; DZ.

Указать все подмножества множества B.

2. Определить значение истинности высказывания

где: P: «Для любого вещественного х выполняется неравенство »;

Q: «Вашингтон - столица США».

3. Упростить формулу:

4. Представить булеву функцию в виде СДНФ с помощью равносильных преобразований:

5. Дана функция:

1) задать эту функцию таблично; 2) найти минимальную ДНФ функции методом карт Карно

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

P(x): «», Q(x): «», если:

R; б).

7. Найти множество истинности предиката, если R:

XII вариант

1. Даны множества:

Найти:

D?N, E \ Z; A?N.

Указать все подмножества множества E.

2. Определить значение истинности высказывания

,

где: P: «Существует наибольшее целое отрицательное число»;

Q: «Для любого вещественного х выполняется: ».

3. Упростить формулу:

4. Представить булеву функцию в виде СДНФ с помощью равносильных преобразований:

5. Дана функция:

1) задать эту функцию таблично; 2) найти минимальную ДНФ функции методом карт Карно.

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

P(x): «», Q(x): «», если:

R; б).

7. Найти множество истинности предиката, если R:

XIII вариант

1. Даны множества:

Найти:

AZ; B?N; DZ.

Указать все подмножества множества B.

2. Определить значение истинности высказывания

где: P: «Для любого вещественного х выполняется неравенство »;

Q: «Санкт-Петербург стоит на Неве».

3. Упростить формулу:

4. Представить булеву функцию в виде СДНФ с помощью равносильных преобразований:

5. Дана функция:

1) задать эту функцию таблично; 2) найти минимальную ДНФ функции методом карт Карно.

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

P(x): «», Q(x): «», если:

R; б).

7. Найти множество истинности предиката, если R:

XIV вариант

1. Даны множества:

Найти:

D?N, E \ Z; A?N.

Указать все подмножества множества E.

2. Определить значение истинности высказывания

,

где: P: «Существует наибольшее целое отрицательное число»;

Q: «Париж - столица Норвегии».

3. Упростить формулу:

4. Представить булеву функцию в виде СДНФ с помощью равносильных преобразований:

5. Дана функция:

1) задать эту функцию таблично; 2) найти минимальную ДНФ функции методом карт Карно.

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

P(x): «», Q(x): «», если:

R; б).

Найти множество истинности предиката, если R:

XV вариант

1. Даны множества:

Найти:

AZ; B?N; DZ.

Указать все подмножества множества B.

2. Определить значение истинности высказывания

где: P: «Для любого вещественного х выполняется неравенство »;

Q: «Нева вытекает из Ладожского озера».

3. Упростить формулу:

4. Представить булеву функцию в виде СДНФ с помощью равносильных преобразований:

5. Дана функция:

1) задать эту функцию таблично; 2) найти минимальную ДНФ функции методом карт Карно.

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

P(x): «», Q(x): «», если:

R; б).

7. Найти множество истинности предиката, если R:

XVI вариант

1. Даны множества:

Найти:

D?N, E \ Z; A?N.

Указать все подмножества множества E.

2. Определить значение истинности высказывания

,

где: P: «Существует наибольшее целое отрицательное число»;

Q: «Нева впадает в Финский залив».

3. Упростить формулу:

4. Представить булеву функцию в виде СДНФ с помощью равносильных преобразований:

5. Дана функция:

1) задать эту функцию таблично; 2) найти минимальную ДНФ функции методом карт Карно.

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

P(x): «», Q(x): «», если:

R; б).

7. Найти множество истинности предиката, если R:

XVII вариант

1. Даны множества:

Найти:

AZ; B?N; DZ.

Указать все подмножества множества B.

2. Определить значение истинности высказывания

где P: «Сумма углов любого треугольника равна 180 градусов»;

Q: «Москва - столица Германии».

3. Упростить формулу:

4. Представить булеву функцию в виде СДНФ с помощью равносильных преобразований:

5. Дана функция:

1) задать эту функцию таблично; 2) найти минимальную ДНФ функции методом карт Карно.

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

P(x): «», Q(x): «», если:

R; б).

7. Найти множество истинности предиката, если R:

XVIII вариант

1. Даны множества:

Найти:

D?N, E \ Z; A?N. Указать все подмножества множества E.

2. Определить значение истинности высказывания

где P: «Сумма углов любого треугольника равна 30 градусов»;

Q: «Берлин - столица Германии».

3. Упростить формулу:

4. Представить булеву функцию в виде СДНФ с помощью равносильных преобразований:

5.Дана функция:

1) задать эту функцию таблично; 2) найти минимальную ДНФ функции методом карт Карно.

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

P(x): «», Q(x): «», если:

R; б).

7.Найти множество истинности предиката, если R:

XIX вариант

1. Даны множества:

Найти:

AZ; B?N; DZ.

Указать все подмножества множества B.

2. Определить значение истинности высказывания

где: P: «Сумма углов любого треугольника равна 180 градусов»;

Q: «Лондон - столица Германии».

3. Упростить формулу:

4. Представить булеву функцию в виде СДНФ с помощью равносильных преобразований:

5. Дана функция:

1) задать эту функцию таблично; 2) найти минимальную ДНФ функции методом карт Карно.

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

P(x): «», Q(x): «», если:

R; б).

7. Найти множество истинности предиката, если R:

XX вариант

1. Даны множества:

Найти:

D?N, E \ Z; A?N. Указать все подмножества множества E.

2. Определить значение истинности высказывания

,

где: P: «Пекин - столица Китая»;

Q: «Для любого вещественного х выполняется: ».

3. Упростить формулу:

4. Представить булеву функцию в виде СДНФ с помощью равносильных преобразований:

5. Дана функция:

1) задать эту функцию таблично; 2) найти минимальную ДНФ функции методом карт Карно.

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

P(x): «», Q(x): «», если:

R; б).

7. Найти множество истинности предиката, если R:

XXI вариант

1. Даны множества:

Найти:

AZ; B?N; DZ.

Указать все подмножества множества B.

2. Определить значение истинности высказывания

где: P: «Для любого вещественного х выполняется неравенство »;

Q: «Вена - столица Австрии».

3. Упростить формулу:

4. Представить булеву функцию в виде СДНФ с помощью равносильных преобразований:

5. Дана функция:

1) задать эту функцию таблично; 2) найти минимальную ДНФ функции методом карт Карно

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

P(x): «», Q(x): «», если:

R; б).

7. Найти множество истинности предиката, если R:

XXII вариант

1. Даны множества:

Найти:

D?N, E \ Z; A?N.

Указать все подмножества множества E.

2. Определить значение истинности высказывания

,

где: P: «Существует наибольшее целое отрицательное число»;

Q: «Киев - столица Украины».

3. Упростить формулу:

4. Представить булеву функцию в виде СДНФ с помощью равносильных преобразований:



5. Дана функция:

1) задать эту функцию таблично; 2) найти минимальную ДНФ функции методом карт Карно.

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

P(x): «», Q(x): «», если:

R; б).

7. Найти множество истинности предиката, если R:

XXIII вариант

1. Даны множества:

Найти:

AZ; B?N; DZ.

Указать все подмножества множества B.

2. Определить значение истинности высказывания

где: P: «Для любого вещественного х выполняется неравенство »;

Q: «Лондон стоит на Темзе».

3. Упростить формулу:

4. Представить булеву функцию в виде СДНФ с помощью равносильных преобразований:

5. Дана функция:

1) задать эту функцию таблично; 2) найти минимальную ДНФ функции методом карт Карно.

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

P(x): «», Q(x): «», если:

R; б).

7. Найти множество истинности предиката, если R:

XXIV вариант

1. Даны множества:

Найти: D?N, E \ Z; A?N. Указать все подмножества множества E.

2. Определить значение истинности высказывания

,

где: P: «Существует наибольшее целое отрицательное число»;