Эквиваленция.

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

Эквиваленция высказываний А, В обозначается символом (или , реже ), читается “для того, чтобы А, необходимо и достаточно, чтобы А”, или “ А тогда и только тогда, когда В”. Высказывания А, В называются . Логические значения операции эквиваленции описываются следующей таблицей истинности:

А	А

 

Например, эквиваленция “Треугольник SPQ с вершиной S и основанием PQ равнобедренный тогда и только тогда, когда P= Q” является истинной, так как высказывания “Треугольник SPQ с вершиной S и основанием PQ равнобедренный” и “В треугольнике SPQ с вершиной S и основанием PQ P= Q” либо одновременно истинны, либо одновременно ложны.

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

 

2.3. Сложные высказывания.

 

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

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

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

 

А	В

 

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

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

Употребление знака равенства для соединения равносильных высказываний совершенно естественно.

Действительно, сложные высказывания и имеют различную форму: из элементарных высказываний А и В они строятся с помощью различных логичных операций. Но для логики высказываний существенно только одно: будет ли при определённом распределении значений истины и лжи для элементарных высказываний составленное из них сложное высказывание истинным или ложным. В этом смысле высказывания и «одинаковы»: если высказываниям А и В приписаны какие-т значения истины или лжи, то высказывания и будут либо оба истинны, либо оба ложны.

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

.

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

А	В

 

 

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

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

.

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

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

 

Приведем основные законы логики высказываний:

 

1. Коммутативность дизъюнкции

.

2. Коммутативность конъюнкции

.

3. Ассоциативность дизъюнкции

.

4. Ассоциативность конъюнкции

.

5. Законы дистрибутивности

, .

6. Законы де Моргана

, .

7. Законы идемпотентности

, .

8. Законы, включающие тождественно истинные (I) и тождественно ложные (L) высказывания

, , , .

9. Закон замены операции импликации

.

10. Законы замены операции эквивалентности

, ,

.

Пример 1. Доказать равносильность:

.

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

.

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

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

 

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

Применение закона 10, даёт доказательство равносильности

.

Пример 2. Упростить высказывание

 

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

.

 

 

Упражнения.

 

№ 1. Установите, какие из следующих предложений являются высказываниями: а) 3+2 = 5; б) 3<2; в) 3£2; г) у²³0; д) «Число слов в этом предложении равно семи»; е) «Осень — лучшая пора года»; ж) «Знаете ли вы украинскую ночь?»; з) «В четырехугольнике противоположные стороны равны»; и) «Во всяком четырехугольнике противоположные стороны равны»; к) «В некоторых четырехугольниках противоположные стороны равны»; л) «Существует число х такое, что х²<0»; м) «В городе N более 100 000 жителей»; н) «Существует наибольшее натуральное число»; 0) H₂O+SO₃=H₂S0₄; п) снег белый; р) белый снег.

 

№2. Сформулируйте отрицания следующих высказываний; ука­жите значения истинности данных высказываний и их отрицаний: а) «Луна — спутник Марса»; б) «32 не делится на 4»; в) 5>2; г) 3£5; д) «Все простые числа нечетны».

 

№3. Определите значения истинности следующих высказываний: а) «Париж расположен на Сене и 2+3 = 5»; б) «1 — простое , число и 2 — простое число»; в) «1 — простое число или 2 — простое число»; г) «Число 2 — четное или это число — простое»; д) 2£3, 2³3, 2·2<4, 2·2>4; е) «2·2=4 или белые медведи живут в Африке»; ж) 2·2 = 4, и 2·2£5, и 2·2³4.

 

№ 4. Определите значения истинности высказываний А, В, С и D если: а) А Ù(2·2 = 4) — истинное высказывание; б) В Ù(2·2 = 4) — ложное высказывание; в) CÚ(2·2 =5) — истинное высказывание; г) D Ú (2·2=5) —ложное высказывание.

 

№5. Пусть p₁ и р₂ — два данных высказывания. С помощью операций отрицания и конъюнкции построить из p₁ и р₂ такое сложное
высказывание р, что

а) р истинно тогда и только тогда, когда p₁ и р₂ оба истинны;

б) р истинно тогда и только тогда, когда р₁ истинно, a р₂ ложно;

в) р истинно тогда и только тогда, когда p₁ и р₂ оба ложны;

г) р ложно тогда и только тогда, когда p₁ и р₂ оба истинны.

 

№6. Пусть p₁ и р₂ — два данных высказывания. С помощью операции отрицания и импликации построить из p₁ и р₂ такое сложное высказывание р, что

а) р ложно тогда и только тогда, когда p₁ и р₂ оба истинны;

б) р ложно тогда и только тогда, когда p₁ истинно, а р₂ ложно;

в) р ложно тогда и только тогда, когда p₁ ложно, а р₂ истинно;

г) р истинно тогда и только тогда, когда p₁ ложно, а р₂ истинно.

 

№ 7. Прочтите следующие символические выражения:

а) ;

б) ;

в) ;

г) ;

д) .

 

№8. Пусть через А обозначено высказывание «9 делится на 3»,
а через В— высказывание «10 делится на 3». Определите значения
истинности следующих высказываний! а) АÞВ; б) ВÞА; в) ÞВ;
г) ÞА;_д) Þ;е) ; ж) АÞ ; з) ВÞ ; и) АÛВ; к) Û л) Û В; и)АÛ .

 

№ 9. Найдется ли такой день недели, когда: а) утверждение «Если сегодня понедельник, то завтра пятница» истинно; б) ут­верждение «Если сегодня понедельник, то завтра вторник» ложно?

 

№ 10. Определите значения истинности следующих высказываний:
а) «Если 12 делится на 6, то 12 делится на 3»; 6) «Если 11 делится
на 6, то 11 делится на 3»; в) «Если 15 делится на 6, то 15 делится
на 3»; г) «Если 15 делится на 3, то 15 делится на 6»; д) «Если Париж расположен на Темзе, то белые медведи обитают в Африке»;

е) «12 делится на 6 тогда итолько тогда, когда 12 делится на 3»;

ж) «11 делится на 6 тогда и только тогда, когда 11 делится на 3»;

з) «15 делится на 6 тогда и только тогда, когда 15 делится на 3»;

и) «15 делится на 5 тогда и только тогда, когда 15 делится на 4»;
к)«Солнце всходит на востоке тогда и только тогда, когда оно
заходит на западе».

 

№11. Определите значения истинности высказываний А, В, С, D в следующих предложениях, первые два из которых истинны, а по­следние два – ложны: а) АÛ(2<3); б) В Û(2>3); в) СÛ (2< 3); г) DÛ(2>3).

 

№ 12. Для следующих формул найти более простые равносильные формулы:

а) ;

б) ;

в) .

 

№13. Четыре студентки — Мария, Нина, Ольга и Полина —
участвовали в соревновании и заняли четыре призовых места.
Когда стали узнавать, как распределились места, получили
три разных ответа:

1) Ольга первая, Нина вторая;

2) Ольга вторая, Полина третья;

3) Мария вторая, Полина четвертая.

Вкаждом ответе, по крайней мере, одна часть верна. Определить правильное распределение мест.

 

 

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

 

3.1. Понятие предиката.

 

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

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

Например, в рассуждении “Всякий ромб – параллелограмм; АВСD – ромб; следовательно, АВСD - параллелограмм ” посылки и заключение являются элементарными высказываниями логики высказываний и с точки зрения этой логики рассматриваются как целые, неделимые, без учета их внутренней структуры. Следовательно, алгебра логики, будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений.

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

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

Логика предикатов расчленяет элементарное высказывание на субъект (буквально – подлежащее, хотя оно может играть и роль дополнения) и предикат (буквально – сказуемое, хотя оно может играть и роль определения). Субъект – это то, о чем что-то утверждается в высказывании;

предикат – это то, что утверждается о субъекте. Например, в высказывании “7 - простое число”, “7” – субъект, “простое число” – предикат. Это высказывание утверждает, что “7” обладает свойством “быть простым числом”.

Если в рассмотренном примере заменить конкретное число 7 переменной х из множества натуральных чисел, то получим высказывательную форму “х – простое число”. При одних значения х (например, х=13, х=17) эта форма дает истинные высказывания, а при других значениях х (например, х=10, х=18) эта форма дает ложные высказывания.

Ясно, что эта высказывательная форма определяет функцию одной переменной х, определенной на множестве N, и принимающую значения из множества {1;0} (или {и; л}). Здесь предикат становится функцией субъекта и выражает свойство субъекта.

Далее даны несколько определений, относящихся к предикатам.

Определение 1.

Одноместным предикатом Р(x) называется произвольная функция переменного x, определенная на множестве M и принимающая значение из множества {1; 0}.

Множество М, на котором определен предикат Р(x), называется областью определения предиката Р(x).

Множество всех элементов , при которых предикат принимает значения “истина” (1), называется множеством (областью) истинности предиката Р(x), т.е. множество истинности предиката Р(х)- это множество .Так, например, предикат Р(x) – “x – простое число” определен на множестве N, а множество истинности I_P для него есть множество всех простых чисел.

Предикат Q(x) – “sinx=0” определен на множестве R, а его множеством истинности является

Предикат F(x) – “диагонали параллелограмма x взаимно перпендикулярны” определен на множестве всех параллелограммов, а его множеством истинности является множество всех ромбов.

Из приведенных примеров видим, что одноместные предикаты выражают свойства предметов (субъектов).

Определение 2.

Предикат Р(х), определенный на множестве М, называется тождественно истинным, если его множество истинности совпадает с областью определения, т. е. I_p=M.

Определение 3.

Предикат Р(х), определенный на множестве М, называется тождественно ложным, если его множество истинности является пустым множеством, т. е. I_p=0.

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

Примером бинарного отношения, т. е. отношения между двумя предметами, является отношение “меньше ”. Пусть это отношение введено на множестве Z целых чисел. Оно может быть охарактеризовано высказывательной формой “х<y”, где , то–есть является функцией двух переменных Р(х,y), определенной на множестве упорядоченных пар целых чисел ZхZ=Z² c множеством значений {1;0}.

Определение 4.

Двухместным предикатом Р(x,y) называется функция двух переменных x и y, определенная на множестве М=М₁хМ₂ и принимающая значения из множества {1;0}.

В числе примеров двухместных предикатов можно назвать такие предикаты: Q(x, y) – “x=y” - предикат равенства, определенный на множестве RхR=R²; F(x,y) – “х параллелен y”, “прямая х параллельна прямой y”, определенный на множестве прямых, лежащих на данной плоскости.

Совершенно аналогично вводится понятие трехместного предиката. Приведем пример трехместного предиката (функции трех переменных): S(x,y,z) – “x+y=z”. Подстановка в него х=3 превращает его в двухместный предикат: S(y,z) – “3+y=z”, а подстановка х=3, z=2 – в одноместный предикат S(y) – “3+y=2”.Подстановка же S(2,3,5) превращает его в истинное высказывание, а S(1,7,4)– в ложное.

Аналогично определяется и n-местный предикат (функция n переменных). Пример n- местного предиката:

R(x₁, x₂,…,x_n): a₁ x₁+…+a_nx_n=0, который, как видим, представляет собой алгебраическое уравнение с n неизвестными.

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

 

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

 

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

Пусть на некотором множестве M определены два предиката P(x) и Q(x).

Определение 5.

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

Очевидно, что областью истинности предиката является общая часть области истинности предикатов P(x) и Q(x), т.е. пересечение .

Так, например, для предикатов P(x): “x – четное число” и Q(x): “x кратно 3” конъюнкцией является предикат “x – четное число и x кратно трем”, т.е. предикат “x делится на 6”.

Определение 6.

Дизъюнкцией двух предикатов P(x) и Q(x) называется новый предикат , который принимает значение “ложь” при тех и только тех значениях , при которых каждый из предикатов принимает значение “ложь”, и принимает значение “истина” во всех остальных случаях.

Ясно, что областью истинности предиката является объединение области истинности предикатов P(x) и Q(x), т.е. .

Определение 7.

Отрицанием предиката P(x) называется новый предикат или , который принимает значение “истина” при всех значениях , при которых предикат P(x) принимает значение “ложь”, и принимает значение “ложь” при тех значениях , при которых предикат P(x) принимает значение “истина”.

Очевидно, что , т.е. множество истинности предиката является дополнением к множеству I_P.

 

Определение 8.

Импликацией предикатов P(x) и Q(x) называется новый предикат , который является ложным при тех и только тех значениях , при которых одновременно P(x) принимает значение “истина”, а Q(x) – значение “ложь”, и принимает значение “истина” во всех остальных случаях.

Поскольку при каждом фиксированном справедлива равносильность , то .

Определение 9.

Эквиваленцией предикатов P(x) и Q(x) называется новый предикат , который обращается в “истину” при всех тех и только тех , при которых P(x) и Q(x) обращаются оба в истинные или оба в ложные высказывания.

Для его множества истинности имеем:

Пример 1. Решить неравенство х² – 8х+15>0.

 

1. .

 

2.

 

 

Ответ: (-¥, 3)È(5, +¥).

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

 

Пример 2. .

Таким образом, конъюнкция предикатов соответствует операции пересечения множеств.

Говорят, что предикат Q(x) логически следует из предиката P(x) , если импликация P(x) Þ Q(x) обращается в истинный предикат при любых наборах значений входящих в него переменных.

При этом множества истинности P(x) и Q(x) таковы, что I_рÌI_Q.

Пример 3. Из равенства х=0 следует равенство х(х—1)=0.

Из равенства (х—1)х=0 не следует равенство х=0, так как при х=1 первое равенство верно, а вто­рое — неверно.

Из равенства х(х—1)=0 следует неравенство х>-1, так как корни 0 и 1 уравнения являются реше­ниями неравенства.

Из неравенства |х|<0 следует любой предикат, так как это неравенство не выполня­ется ни при каком значении переменной, и поэтому предикат |х|<0ÞР(х) является истинным при любых значениях входящих в него переменных.

Из формы «х — сын у и z» следует форма «у и z — родители х», но из формы «у и z—родители х» не следует форма «х — сын у и z», так как существует на­бор значений переменных (дочь, отец, мать), при кото­рых форма «у и z — родители х» становится истинным высказыванием, а форма «х — сын у и z» — ложным высказыванием.

Пример 4. Для эквивалентности предикатов P(x) Û Q(x) их множества истинности должны совпадать, т.е. I_р=I_Q (возможно, что оба множества будут пустыми). Например, 4х-2=6 Ûх-2=0 или Û х+1=х.

3.3. Кванторные операции.

 

Рассмотрим операции, преобразующие предикаты в высказывания.

Пусть имеется предикат Р(х) определенный на множестве М. Если “а” – некоторый элемент из множества М, то подстановка его вместо х в предикат Р(х) превращает этот предикат в высказывание Р(а). Такое высказывание называют единичным. Например, р(x): “х – четное число” – предикат, а р(6)- истинное высказывание, р(3) – ложное высказывание.

Это же относится и к n-местным предикатам: если вместо всех предметных переменных х_i, i= подставить их значения, то получим высказывание.

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