Методическая разработка «ОСНОВНЫЕ ПОНЯТИЯ МАТЕМАТИЧЕСКОЙ ЛОГИКИ»
Государственное бюджетное общеобразовательное учреждение лицей № 393 Кировского района Санкт-Петербурга
МЕТОДИЧЕСКАЯ РАЗРАБОТКА
«ОСНОВНЫЕ ПОНЯТИЯ МАТЕМАТИЧЕСКОЙ ЛОГИКИ»
Подготовил
учитель информатики
Смирнов Игорь Александрович
г. Санкт-Петербург 2016
ВЫСКАЗЫВАНИЯ И ЛОГИЧЕСКИЕ ОПЕРАЦИИ НАД НИМИ
ОПРЕДЕЛЕНИЕ. Высказывание - это повествовательное предложение о котором можно сказать однозначно истинно оно или ложно.
Задание: Какие из следующих предложении являются высказываниями?
1. Стой! Куда идёшь?
2. Нева впадает в Черное море.
3. Да здравствуют учащиеся школы № 139!
4. A > 0
5. 2+ 13 EMBED Equation.3 1415
6. 15 - простое число
2х -1-3 = 1
8. В романе "Евгений Онегин” 12 234 567 букв
9. Маслины вкуснее ананасов.
10. Картины Пикассо слишком абстрактны
11.Для любого натурального числа n найдутся целые числа x, у и z такие, что xn+yn=zn.
1,3,4,5,7,9,10- не высказывания; 2,6,8,11 – высказывания;
Для обозначения высказываний мы будем использовать заглавные латинские буквы: А,В,С,D,... Если А - некоторое высказывание, то запись A=True, A = 1 или A = И означает, что высказывание А - истинно. Запись A=False, A= 0 или A = Л означает, что высказывание А - ложно.
Из простых высказывании можно строить сложные, составные. В математике наиболее часто использует для этого грамматические связки: "не", "или", "и", "тогда и только тогда", "если..., то...". Построение из одних выска зывании новых высказываний называется логическими операциями над исходными высказываниями. Чтобы придать указанным выше логическим связкам точный смысл, надо условиться, в каких случаях из данных высказываний получается ложное, а в каких истинное высказывание. При этом мы будем исходить только из истинности или ложности исходных высказываний. Итак дадим опре деление основных логических операций над высказываниями.
ОПРЕДЕЛЕНИЕ. Отрицанием высказывания А называется новое высказывание, обозначаемое 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415 ( или 13 EMBED Equation.3 1415 ), читаемое "неверно, что А" или короче "не А", которое истинно, если А ложно, и ложно, если А истинно.
Зависимость значения истинности высказывания А от значения истинности высказывания А можно выразить с помощью таблицы, называемой таблицей
истинности .
Таблица истинности отрицания.
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415 13 EMBED Equation.3 1415
И
Л
Л
И
Пример: 13 EMBED Equation.3 1415= ”2 - простое число “
13 EMBED Equation.3 1415 13 EMBED Equation.3 1415 - "2 не является простым числом” или "неверно, что 2 простое число".
ОПРЕДЕЛЕНИЕ: Конъюнкцией двух высказываний А к В называется новое высказывание, которое обозначается A 13 EMBED Equation.3 1415 B ( или A & B ) , читается "A и В” и которое истинно, если истины оба высказывания А и В и ложно во всех остальных случаях.
Операцию конъюнкция иногда называет логическим умножением, а высказывания А и В членами конъюнкции или сомножителями.
Название конъюнкция происходит от английского слова conjunction
соединение, совпадение.
Пример: Прогноз погоды на завтра "завтра по области будет дождь и температура понизится до 10°". Логично считать прогноз оправданным, если и дождь будет и температура понизится, и неправильным во всех остальных случаях.
Таблица истинности конъюнкции:
A
B
A 13 EMBED Equation.3 1415 B
И
И
И
И
Л
Л
Л
И
Л
Л
Л
Л
Задание: Определить истинны ли следующие высказывания:
1.Санкт-Петербург расположен на Неве и 9 - простое число
И13 EMBED Equation.3 1415Л=Л
2. 2*2=4 и снег – белый
И13 EMBED Equation.3 1415И=И
3. 2*2=5 и 4813 EMBED Equation.3 14155
Л13 EMBED Equation.3 1415Л=Л
В школе вы неоднократно встречались с конъюнкцией и привыкли для ее обозначения использовать знак системы: 4<7< 9 это конъюнкция двух высказываний. Это можно записать: (4 < 7) 13 EMBED Equation.3 1415 (7 < 9) или 13 EMBED Equation.3 1415.
Из определения конъюнкции следует, что союз “и” в алгебре высказываний употребляется в привычном смысле как и в обычной речи.
Если союз "и" употребляется в одном смысле, то союз “или” в русском языке может употребляться в двух смыслах: в смысле исключающем и неисключающем.
Пример: Студенты готовятся к экзамену по учебникам или по конспектам. Сегодня в 19 часов я пойду в кино или в театр. И первом случае подготовка к экзамену по конспектам не исключает использования учебника и наоборот. Во втором случае может быть верна лишь одна возможность; театр или кино.
ОПРЕДЕЛЕНИЕ: Дизъюнкцией высказываний А и В называется новое высказывая которое обозначается А 13 EMBED Equation.3 1415 B, читается “А или В” и которое истинно, если истинно хотя бы одно из высказываний А и B и ложно, если оба высказывания ложны. Операцию дизъюнкция иногда называют логическим сложением, а высказывания А и В - членами дизъюнкции или слагаемыми.
Название дизъюнкция происходит от английского олова disjunction - разъединение, разобщение.
Пример: 2x2=4 или белые медведи живут в Африке – истинно. Из определения видно, что союз или используется в неисключающем смысле. Число 2 - четное или 2 – нечетное. – истинно.
Таблица истинности дизъюнкции:
A
B
A 13 EMBED Equation.3 1415 B
И
И
И
И
Л
И
Л
И
И
Л
Л
Л
В школе вы так же встречались с дизъюнкцией: 213 EMBED Equation.3 14152 - это дизъюнкция двух высказываний 2<2 и 2 = 2, 713 EMBED Equation.3 14153 - это дизъюнкция двух высказываний 7<3 и 7=3.
Для записи дизъюнкции используют также знак “совокупности” 13 EMBED Equation.3 1415
Перед определением следующей операции рассмотрим пример, показывающий целесообразность этого определения.
"Отец оказал сыну: Если я получу премию, то я куплю тебе велосипед”. Обозначим: А – “я получу премию”, В –“я куплю тебе велосипед”. Тогда обещание отца запишем так: А13 EMBED Equation.3 1415В. Еcли ребенок будет считать, что отец одержал слово, то высказывание А13 EMBED Equation.3 1415В целесообразно считать истинным, если нет, - ложным.
Рассмотрим варианты:
Получена премия, куплен велосипед - слово сдержано.
Не получена премия и не куплен велосипед - cлово сдержано.
Не получена премия, но велосипед куплен - поступок отца не является нарушением обещания.
Получена премия, а велосипед не куплен - обещание не выполнено, ребенок считает себя обманутым. Этот пример показывает целесообразность введения следующего определения.
ОПРЕДЕЛЕНИЕ. Импликацией двух высказываний А и В называется новое высказывание обозначаемое А13 EMBED Equation.3 1415В, читается “если А, то В” или “из А следует В”, которое ложно лишь в одном случае: когда А истинно, а В ложно и истинно во всех остальных случаях. Высказывание А называется условием или посылкой а высказывание В - заключением или следствием.
Название импликация происходит от английского слова implication - вовлечение, заключение в себя.
Таблица истинности импликации.
A
B
A 13 EMBED Equation.3 1415 B
И
И
И
И
Л
Л
Л
И
И
Л
Л
И
Задание: Определить истинны ли следующие высказывания
Если 2*2=5, то снег черный.
Л13 EMBED Equation.3 1415Л=И
Если 2*2=5, то 6 делится на 3.
Л13 EMBED Equation.3 1415И=И
Если 2 меньше 3, то 3 меньше нуля.
Л13 EMBED Equation.3 1415Л=И
В обычной речи мы привыкли, что слова “из А следует B“ предполагает, что между А и В существует некая зависи мость, в силу которой высказывание А может быть как-то получено из В. Тогда первый пример есть высказывание не имеющее смысла. Но определение импликации позволяет рассматривать импликацию двух любых высказываний и определять логическое значение такой импликации. Значение импликации для математических доказательств состоит в том, что из истинности импликации и её посылки мы можем сделать вывод об истинности её заключения.
Задание: пусть истинна импликация: “Еcли 4 - четное числе, то А”. Каково логическое значение высказывания А?
И13 EMBED Equation.3 1415A=И, тогда А=И
ОПРЕДЕЛЕНИЕ. Эквивалентностью двух высказываний А и B называется новое высказывание обозначаемое А 13 EMBED Equation.3 1415В, читается "А эквивалентно B” или "А равносильно B” или "А тогда и только тогда, когда B”, которое считается истинным, если А и В одновременно оба истинны или оба ложны, а в остальных случаях ложно. А и В называются членами эквивалентности. Название эквивалентность происходит от английского слова equivalence - равноценность, эквивалентность.
Таблица истинности эквивалентности.
A
B
A 13 EMBED Equation.3 1415 B
И
И
И
И
Л
Л
Л
И
Л
Л
Л
И
Примеры:
Натуральное число n делится на 3 тогда и только тогда когда сумма его цифр делится на 3. - истина
2=3 тогда и только тогда, когда 5 больше 6. - истина
Значение эквивалентности для математических доказательств в том, что из ис тинности эквивалентности одного из её членов можно сделать вывод об истинности другого её члена.
Задания для самостоятельного решения:
Определите истинностное значение высказываний:
Если 12 делится на 6 , то 12 делится на 3.
Если 11 делится на 6 , то 11 делится на 3.
Если 15 делится на 6 , то 15 делится на 3.
Если 15 делится на 3 , то 15 делится на 6.
12 делится на 6, тогда и только тогда, когда 12 делится на 3.
11 делится на 6, тогда и только тогда, когда 11 делится на 3.
15 делится на 6, тогда и только тогда, когда 15 делится на 3.
2. Каково истинностное значение высказывания А, если истинно высказывание:
А и 2*2=4
А или 2*2=5
Если А, то 4 - нечетное число
Если 3>2, то 613 EMBED Equation.3 14152 и А
Если 1313 EMBED Equation.3 141513 и А, то 4 >7
Если 1213 EMBED Equation.3 14153, то А или 313 EMBED Equation.3 14152
Если А или 613 EMBED Equation.3 14152, то 813 EMBED Equation.3 14152 и A
3.Каково истинностное значение высказывания А, если ложно высказы вание:
A и 2*2=4
А или 2*2=5
А и 2*2=5
Еcли 2 - четно, то А
Еcли А, то 4 - нечетное число
Если А или 613 EMBED Equation.3 14153, то 813 EMBED Equation.3 141510 и А
Если 6 > 7 и А, то 1213 EMBED Equation.3 14154 и А
Если 413 EMBED Equation.3 14152 и А, то 12> 2 и А
4.Найдите истинностные значения высказываний
((22<4)13 EMBED Equation.3 1415(7>5)13 EMBED Equation.3 141513 EMBED Equation
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
5.Определите, кто из четырех студентов сдал экзамен, если известно:
1. Если первый сдал, то и второй сдал.
2. Если второй сдал, то третий сдал или первый не сдал.
3. Если четвертый не сдал, то первый сдал, а третий не сдал.
4. Если четвертый сдал, то и первый сдал.
6.На вопрос: кто из трех студентов изучал математичес кую логику, получен верный ответ: "Если изучал первый, то изучал и третий, но неверно, что если изучал второй, то изучал и третий". Кто изучал математическую логику?
ЛОГИЧЕСКИЕ ФОРМУЛЫ, РАВНОСИЛЬНОСТЬ ЛОГИЧЕСКИХ ФОРМУЛ.
Понятие логической формулы. Разговор о расстановке скобок.
В общем курсе математической логики есть строгое определение понятия логической формулы. Мы в нашем курсе не будем давать строгого определения, а для формирования данного понятия проведем аналогию с понятием формул и алгебраических выражений в школьном курсе алгебры.
Известно, что и в арифметике и в алгебре мы используем 4 действия: сло жение, умножение, вычитание и деление. Иcпользуя эти действия и "правильно" расставив скобки, мы можем из чисел и букв составить сложные арифметические и алгебраические выражения, в которых используется несколько действий.
Пример: ((1-2): 3 + 4)*5
1-( 2:3 + 4 )*5
1-2:(3 + 4*5)
Замечание. Приведем пример “неправильно” расставленных скобок: ((2(+)3)*5(
Мы видим, что используя одни и те же числа и действия мы получили выражения, имеющие разное значения в зависимости от расстановки скобок, то есть от последовательности выполнения действий. В некоторых местах скобки не постав лены, так как есть договоренность о том, что действия деление и умно жения выполняются раньше, чем сложение и вычитание.
Рассмотрим алгебраические выражения: (а - в) + с и а - (в + с). Если в данные алгебраические выражения вместо переменных а, в ,с подставлять одинаковые наборы значений этих переменных, то ясно, что результаты будут вообще говоря разные ( хотя при некоторых наборах значений, например при a=в=c=0, их значения совпадут). Таким образом, и в числовых и в алгебраичес ких выражениях скобки играют существенную роль. Если скобки не поставлены и нет никаких договоренностей о последовательности выполнения основных действий, то на самом деле просто нельзя вычислить значение ни одного алгебраического выражения.
В математической логике , по аналогии с алгебраическими выражениями, мы мо жем составить из простых высказываний сложные, используя основные логичес кие операции и скобки «Если все скобки расставлены "правильно", то можно вычислить значение полученного сложного высказывания, если известны логические значения входящих в него простых высказываний. Такие сложные высказыванья мы будем называть логическими формулами.
Например, запись А13 EMBED Equation.3 1415В13 EMBED Equation.3 1415С - не является логической формулой, так как не ясна последовательность выполнения логической операции импликация. Выражения (А13 EMBED Equation.3 1415В)13 EMBED Equation.3 1415С и А13 EMBED Equation.3 1415(В13 EMBED Equation.3 1415С) - являются логическими формулами. Видно, что это разные высказывания, так как при одинаковых значе ниях входящих в формулу логических переменных А,В, С они могут принимать разные логические значения. Например, если A=B=C=Л, то (А13 EMBED Equation.3 1415В)13 EMBED Equation.3 1415С =Л, а А13 EMBED Equation.3 1415(В13 EMBED Equation.3 1415С)=И.
Задание: Вычислить логическое значение формул при A = И, B = С= Л
a) (А13 EMBED Equation.3 1415В) 13 EMBED Equation.3 1415 (С 13 EMBED Equation.3 1415В)
(И13 EMBED Equation.3 1415Л) =И; (Л 13 EMBED Equation.3 1415Л)=Л; (И13 EMBED Equation.3 1415Л) =Л;
b) (A13 EMBED Equation.3 1415( В 13 EMBED Equation.3 1415С) 13 EMBED Equation.3 1415B)
(Л13 EMBED Equation.3 1415Л)=И; (И13 EMBED Equation.3 1415И)=И; (И13 EMBED Equation.3 1415Л)=Л;
c) A13 EMBED Equation.3 1415((B13 EMBED Equation.3 1415C)13 EMBED Equation.3 1415B)
Л13 EMBED Equation.3 1415Л=Л; (Л13 EMBED Equation.3 1415Л)=Л; (И13 EMBED Equation.3 1415Л)=И;
Любое сложное высказывание можно разбить на простые и записать его в виде логической формулы. При этом надо учитывать, что в русском языке вместе сою зов "и" и "или" и связок "если..., то...", "тогда и только тогда" могут быть использованы другие союзы и связки. Умение видеть какая логическая операция стоит за тем или иным союзом или связкой очень важно.
Задание: Следующие составные высказывания расчлените на простые и запишите с использо ванием знаков логических операций, введя обозначения для простых высказываний.
a) Если мы поедем летом в Париж и у нас будет достаточно времени, то мы посетим Лувр.
A- мы поедем летом в Париж; B- у нас будет время; C- мы посетим Лувр;
ABC
b) Если мы скоро окончим работу и будет хорошая погода, то мы пойдем на про гулку или поедем на пляж.
A- скоро окончим работу; B- будет хорошая погода; C- пойдем на про гулку; D- поедем на пляж;
(AB) (C13 EMBED Equation.3 1415D)
c) Если мистер Смиттенгольдц счастлив, то миссис Смиттенгольдц несчастлива, и если мистер Смиттенгольдц несчастлив, то миссис Смиттенгольдц счастлива.
A- мистер Смиттенгольдц счастлив; B- миссис Смиттенгольдц счастлива;
(AB) (13 EMBED Equation.3 1415AB)
d) Если летом будет дождливая погода, то ни накупаться нам не удастся, ни загорать нам не удастся.
A- будет дождливая погода;B- удастся накупаться; C- удастся загорать;
A 13 EMBED Equation.3 1415 (BC)
Равносильные формулы.
Запишем на языке логических формул два сложных высказывания.
1. Неверно, что завтра будет дождь и температура воздуха понизится до 100
2. 3автра не будет дождя или температура не понизится до 10°
Одна и та же информация заключена в этих двух высказываниях или нет?
Попробуем рассмотреть это формально. Обозначим: А -"завтра будет дождь"; В - "завтра температура воздуха понизится до 100".
Тогда высказывания примут вид: F1=(A13 EMBED Equation.3 1415B) и F2=13 EMBED Equation.3 1415A13 EMBED Equation.3 1415B
Составим таблицы истинности этих формул, то есть рассмотрим какие значения принимают эти формулы при всевозможных наборах значений переменных А и В.
A
B
(A13 EMBED Equation.3 1415B)
13 EMBED Equation.3 1415A13 EMBED Equation.3 1415B
И
И
Л
Л
И
Л
И
И
Л
И
И
И
Л
Л
И
И
И по смыслу и по таблицам видно, что эти формулы выражают одно и тоже содержание.
ОПРЕДЕЛЕНИЕ. Пусть даны две логические формулы, содержание одни и те же переменные A1,A2,A3,An. Формулы называются равносильными, если при любых логических значениях переменных A1,A2,A3,An логические значения данных формул совпадают.
Для обозначения равносильности формул можно использовать значки или 13 EMBED Equation.3 1415.
В нашем примере мы доказали, что рассматриваемые нами формулы равносильны, то есть
F1 (A1,A2,A3,An ) F2(A1,A2,A3,An )
Из определения следует, что для того, чтобы доказать равносильность формул достаточно составить таблицы истинности для этих формул и убедиться, что во всех случаях формулы принимают одни и те же логические значения.
Рассмотрим основные пары равносильных формул.
закон двойного отрицания 13 EMBED Equation.3 1415(13 EMBED Equation.3 1415A)13 EMBED Equation.3 1415A
законы Моргана 13 EMBED Equation.3 1415(A13 EMBED Equation.3 1415B)13 EMBED Equation.3 141513 EMBED Equation.3 1415A13 EMBED Equation.3 141513 EMBED Equation.3 1415B
13 EMBED Equation.3 1415(A13 EMBED Equation.3 1415B)13 EMBED Equation.3 141513 EMBED Equation.3 1415A13 EMBED Equation.3 141513 EMBED Equation.3 1415B
законы идемпотентности A13 EMBED Equation.3 1415A13 EMBED Equation.3 1415A
A13 EMBED Equation.3 1415A13 EMBED Equation.3 1415A
законы коммутативности A13 EMBED Equation.3 1415B13 EMBED Equation.3 1415B13 EMBED Equation.3 1415A
A13 EMBED Equation.3 1415B13 EMBED Equation.3 1415B13 EMBED Equation.3 1415A
законы ассоциативности (A13 EMBED Equation.3 1415B)13 EMBED Equation.3 1415C13 EMBED Equation.3 1415(A13 EMBED Equation.3 1415C)13 EMBED Equation.3 1415(B13 EMBED Equation.3 1415C) (A13 EMBED Equation.3 1415B)13 EMBED Equation.3 1415C13 EMBED Equation.3 1415(A13 EMBED Equation.3 1415C)13 EMBED Equation.3 1415(B13 EMBED Equation.3 1415C)
законы дистрибутивности A13 EMBED Equation.3 1415(B13 EMBED Equation.3 1415C) 13 EMBED Equation.3 1415(A13 EMBED Equation.3 1415B)13 EMBED Equation.3 1415(A13 EMBED Equation.3 1415C)
A13 EMBED Equation.3 1415(B13 EMBED Equation.3 1415C) 13 EMBED Equation.3 1415(A13 EMBED Equation.3 1415B)13 EMBED Equation.3 1415(A13 EMBED Equation.3 1415C)
законы поглощения A13 EMBED Equation.3 1415(B13 EMBED Equation.3 1415A) 13 EMBED Equation.3 1415A
A13 EMBED Equation.3 1415(B 13 EMBED Equation.3 1415A) 13 EMBED Equation.3 1415A
A13 EMBED Equation.3 1415И 13 EMBED Equation.3 1415 И
A13 EMBED Equation.3 1415Л 13 EMBED Equation.3 1415 A
A13 EMBED Equation.3 1415И 13 EMBED Equation.3 1415 A
A13 EMBED Equation.3 1415Л 13 EMBED Equation.3 1415 Л
A 13 EMBED Equation.3 1415B 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415A 13 EMBED Equation.3 1415B
Все данные законы можно доказать используя таблицу истинности. Используя данные законы можно из сложных формул получать равносильные им формулы, имеющие более простой вид, то есть как в алгебре, решать задачи типа:"упростить выражение". При этом выделив в преобразуемой формуле некоторую"подформулу" мы можем применить к ней перечисленные законы, то есть заменить ее на равносильную, подобно тому как в преоб разованиях алгебраических выражений мы используем формулы сокращенного умножения.
Задание. На занятиях по математической логике студентам было предложено запи сать с помощью логических операций и простых высказываний следующее высказы вание: "Если сегодня не выходной, то Коля идет в школу, если у него нет вы сокой температуры”. Студенты ввели обозначения для простых высказываний: А - сегодня выходной день, В - Коля идет в школу, С - у Коли нет высокой тем пературы. Два студента составили различные формула, соответствующие данному высказыванию:
1) 13 EMBED Equation.3 1415A13 EMBED Equation.3 1415(C13 EMBED Equation.3 1415B) 2)(A13 EMBED Equation.3 1415C)13 EMBED Equation.3 1415B
Доказать, что данные формулы равносильны.
Первый способ:
13 EMBED Equation.3 1415A13 EMBED Equation.3 1415(C13 EMBED Equation.3 1415B) 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415(13 EMBED Equation.3 1415A)13 EMBED Equation.3 1415(13 EMBED Equati
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·Мы видим, что обе формулы равносильны одной и той же третьей формуле, а значит, равносильны между собой.
Второй способ.
Составим таблицу истинностных значений обеих формул при всевозможных уходящих в них простых высказываний.
A
B
C
13 EMBED Equation.3 1415A13 EMBED Equation.3 1415(C13 EMBED Equation.3 1415B)
(A13 EMBED Equation.3 1415C)13 EMBED Equation.3 1415B
И
И
И
И
И
И
И
Л
И
И
И
Л
И
И
И
И
Л
Л
И
И
Л
И
И
И
И
Л
И
Л
И
И
Л
Л
И
Л
Л
Л
Л
Л
И
И
Видим, что таблицы истинности формул совпадают, значит формулы равносильны.
Задания для самостоятельного решения:
7. Следующие составные высказывания расчлените на простые и запишите с использо ванием знаков логических операций, введя обозначения для простых высказываний.
Если ни в Париж мы не поедем, ни в горы мы не отправимся, то мы ежедневно будем ходить на пляж, или если будет дождь, то мы будем читать дома книги.
Если бы Платон был в Египте и видел там пирамиды, то они бы его очень заинтере совали, или если бы кто-нибудь обратил на них его внимание, и ему было бы объяснено их устройство, то они могли бы произвести на него неизгладимое впечатление.
Если я поеду в деревню тогда и только тогда, когда сдам экзамен, то если я не сдам экзамен, то я останусь в городе
Если "Спартак" и "Локомотив " проиграют, а "Зенит" выиграет, то "ЦСКА" по теряет первое место, а на третье место выйдет "Торпедо
8. Упростить формулы.
13 EMBED Equation.3 1415(13 EMBED Equation.3 1415A13 EMBED Equation.3 141513 EMBED Equation.3 1415B)13 EMBED Equation.3 1415((A13 EMBED Equation.3 1415B)13 EMBED Eq
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
· При составлении расписания уроков учителя истории, математики и литературы попросили завуча поставить им их уроки в среду: математи ку - первым или вторым, историю - первым или третьим; литературу - вторым или третьим. Как используя средства математической логики сос тавить расписание на среду учитывая все пожелания.
Указание: При решении введем следующие обозначения:
Mi - математика стоит i-м уроком
Иi - история стоит i-м уроком
Лi - литература стоит i-м уроком
10. Студент решил во время каникул прочитать не менее двух книг, сходить в театр или на концерт и, если выпадет снег, съездить на лыжную прогулку. Когда можно считать, что не выполнил свое решение.
Указание: При решении введем следующие обозначения:
A - прочитал не менее двух книг
B - сходил в театр
C - сходил на концерт
D - выпал снег
E - съездил на лыжную прогулку
11.В школу, в которой вы работаете, пришел строгий приказ о запрещении курить в помещении школы. Внезапно стало известно, что из инстанции издавший приказ в школу едет инспектор, который привык курить где попало и постоянно. Директор, у которого не все в порядке с математической логикой издает указание по школе:
« В школе должно быть выполнено одно из условий:
инспектору не разрешается курить в школе
если инспектору разрешается курить в школе, то ученики должны быть предупреждены об этом и учителя должны принять меры для быстрого уничтожения окурков
ученики должны быть предупреждены об этом или учителя должны принять меры для быстрого уничтожения окурков
или ученики должны быть предупреждены об этом и учителя должны принять меры для быстрого уничтожения окурков, или инспектору не разрешается курить в школе
Как используя средства математической логики упростить директиву директора?
МНОЖЕСТВА.
Множество - основное математическое понятие, не определяемое. Можно дать лишь описание его. Множество - это совокупность, набор, класс некоторых предметов, объединенных по какому-то принципу, и рассматриваемое как единое целое.
Предметы, из которых состоит множество ,называют его элементами. Если эле мент а входит в множество А, то говорят, что элемент а принадлежит множеству А и обозначают: а13 EMBED Equation.3 1415А. Если элемент а не входит в множество А, то пишут а13 EMBED Equation.3 1415 А. Заметим: для любых конкретных а и А: а13 EMBED Equation.3 1415А - это высказывание, истинное или ложное.
Пример:
В.В.Путин 13 EMBED Equation.3 1415 множеству учеников школы № 139
Ученица Пышкина 13 EMBED Equation.3 1415 множеству президентов США;
Множество считается вполне определенным, если относительно любого объекта можно твердо установить, принадлежит он этому множеству, или нет.
Примеры. Русский алфавит: А,Б,В,Г,Д,..., Э,Ю,Я
1,2,3,4, - множество натуральных чисел
Множество произведений А.C.Пушкина
Множество студентов
Множество окон в кабинете №38 школы №139
Для обозначения множеств используются заглавные буквы латинского алфавита, а для элементов множеств - прописные буквы латинского алфавита.
Русское слово "множество” может ввести в заблуждение. Оно предполагает не которое изобилие. Однако математическое понятие "множество" этого оттенка может не иметь. Оно может состоять из одного-двух элементов.
Например, множество корней уравнения x2-3x+2 = 0 состоит из двух элементов 1,2. Множество корней уравнения 3x-6=0 - из одного элемента - 2.
В математике целесообразно рассматривать множества, которые не содержат ни одного элемента. Такое множество называется пустым и обозначается - Ш.
Примеры: 13 EMBED Equation.3 1415Множество квадратных колес, множество вечных двигателей,
множество вещест венных корней уравнения x2+1=0.
При работе с множествами следует иметь в виду, что порядок, в котором записаны элементы того или иного множества не играет никакой роли для множества Множество букв русского алфавита принято записывать в определенном порядке: А,Б,В,...,Я, но на клавиатуре пишущей машинки буквы расположены в другом порядке, но множество их то же самое. Множество всех вещественных чисел, находящихся между 0 и 1 вообще нельзя записать по порядку, так как неизвестно какое число в этом множестве самое маленькое.
Отметим, что ни один элемент не может содержаться в множестве несколько раз. Если в русском алфавите мы запишем букву А 53 раза количество букв в алфа вите от этого не увеличится.
Способы задания множества.
Задать множество можно перечислением его элементов. При этом элементы, из которых состоит множество записывают в одну строчку через запятую и огра ничивают эту строку фигурными скобками.
Например, множество корней квадратного уравнения x2-3x+2 = 0 можно записать так : {1,2}.
Ясно, что перечислением можно задать только конечное множество, да и не всегда. Например, множество персонажей романа "Война и мир" конечно, но содержит слишком много элементов, чтобы задать его перечислением. Использовать указанный выше способ записи можно в некоторых случаях и для бесконечных множеств. При задании множества достаточно иногда перечислить несколько элементов, если понятно как продолжить запись.
Например, {1, 2, 3, 4, 5, ...} - ясно, что это все натуральные числа
{2, 4, 6, 8, 10,}- множество всех четных натуральных чисел
Чаще всего множество задают с помощью характеристического (определяющего) свойства, то есть такого свойства, которым обладает каждый элемент данного множества и не обладает ни один элемент этому множеству не принадле жащий. Это свойство может быть описано словами: "все персонажи романа "Война и мир”, "все положительные вещественные числа”. Можно записать свойство в виде неравенства: |3x|<1 и т.д. Чуть ниже мы еще раз остановимся на этом способе задания множеств.
В математике для многих множеств введены специальные обозначения:
N - множество натуральных чисел
Z - множество целых чисел
Q - множество рациональных чисел
R - множество вещественных (действительных) чисел
[a,b] - множество всех вещественных чисел: а13 EMBED Equation.3 1415xb
[a,b) - множество всех вещественных чисел: а13 EMBED Equation.3 1415x
(a,b) - множество всех вещественных чисел: а
(a,b] - множество всех вещественных чисел: а
(-13 EMBED Equation.3 1415,b] - множество всех вещественных чисел: xb
(a, 13 EMBED Equation.3 1415] - множество всех вещественных чисел: а
Подмножества.
Рассмотрим слово МНОЖЕСТВА как совокупность букв, из которых оно состоит
{ м, н, о, ж , е, с, т, в, o}
Поиграем теперь в детскую игру " в слова", то есть из букв данного слова попробуем составить новые слова.
{н,о,ж},{н,о,с},{с,о,н},{ж,е,н,а},{ж,е,т,о,н},{м,а,н,е,ж},{м,о,н,е,т,а},{ж,е,м,а,н,с,т,в,о}
Каждая буква нового слова входит в исходное, то есть каждый элемент вновь построенного множества принадлежит исходному.
ОПРЕДЕЛЕНИЕ. Говорят, что множество А называется подмножеством множества
В, если каждый элемент множества A является элементом множества В.
Обозначение: А В.
Следовательно, можно записать:
{н,о,ж}{ м, н, о, ж , е, с, т, в, o}
{ж,е,т,о,н}{ м, н, о, ж , е, с, т, в, o}
{с,о,н}{н,о,с}
{н,о,с}{с,о,н}
{ж,е,м,а,н,с,т,в,о}{ м, н, о, ж , е, с, т, в, o}
{ м, н, о, ж , е, с, т, в, o}{ж,е,м,а,н,с,т,в,о}
Обратите внимание, на последние 4 примера. Очевидно, что множества букв слов сон и нос, множества и жеманство совпадают.
ОПРЕДЕЛЕНИЕ. Множества А и В называются равными, если они состоят из одних и тех же элементов. При этом пишут: А=B
Очевидно, что А = B тогда и только тогда, когда А В и B A. Таким образом для доказательства равенства множеств необходимо показать, что каждый элемент первого множества содержится во втором и каждый элемент второго - в первом. Таким образом мы можем записать, что {н,о,с}={с,о,н}и т.д.
Следует отметить, что пустое множество по определению считается подмножест вом любого другого множества.
Рассмотрим наиболее типичные ошибки, допускаемые при изучении основных понятий, связанных с множествами.
Во-первых, необходимо различать знаки 13 EMBED Equation.3 1415 и . В высказывании а 13 EMBED Equation.3 1415А знак 13 EMBED Equation.3 1415 стоит между разнородными объектами: элемент и множество, в высказывании А B знак стоит между двумя множествами. Во-вторых, необходимо различать записи: {а} и а, для некоторого элемента а, и записи {A} и А для некоторого множества A. {а}13 EMBED Equation.3 1415а, так как слева одноэлементное множества, а справа отдельный эле мент. {A}13 EMBED Equation.3 1415 А так как слева множество А, состоящее из каких-то элементов, а справа одноэлементное множество, единственным элементом которого является - само множество А.
Примеры. 1) 113 EMBED Equation.3 1415N – истина; 113 EMBED Equation.3 1415{N} – ложь;
2) Пусть A={a,b}, тогда a13 EMBED Equation.3 1415A – истина;{A}={a,b}- ложь; a13 EMBED Equation.3 1415{A} – ложь;
Задания для самостоятельного решения:
11.Выясните какие из следующих высказываний истинны, а какие ложны.
{1,2,3}={3,2,2,1}
{1,{2,3}}={1,2,3}
{{1,2}}={1,2}
{1,2}13 EMBED Equation.3 1415{{1,2,3},{1,3},1,2}
{1,2}13 EMBED Equation.3 1415{{1,2,3},{1,3},1,2}
{1,2}13 EMBED Equation.3 1415{{1,2},3,4}
{1,2}13 EMBED Equation.3 1415{{1,2},3,4}
{1,2}13 EMBED Equation.3 1415{1,2}
113 EMBED Equation.3 1415{1}
113 EMBED Equation.3 1415{1}
Ш13 EMBED Equation.3 1415{ Ш,{ Ш }}
Ш 13 EMBED Equation.3 1415{{ Ш }}
Ш 13 EMBED Equation.3 1415{ Ш,{ Ш }}
Ш ={ Ш }
Ш 13 EMBED Equation.3 1415{{ Ш }}
{ Ш }13 EMBED Equation.3 1415{{ Ш }}
12. Выпишите все подмножества множества {1,2,3}. Для каких четырех различных подмножеств A, B, C, D истинно (A13 EMBED Equation.3 1415B)13 EMBED Equation.3 1415(C 13 EMBED Equation.3 1415D)13 EMBED Equation.3 1415(D13 EMBED Equation.3 1415A)?
13. Для каждого из следующих наборов условий приведите примеры непустых различных множеств A,B,C,D,E, удовлетворяющих всем этим условиям.
D13 EMBED Equation.3 1415C, E13 EMBED Equation.3 1415A, B13 EMBED Equation.3 1415D, A13 EMBED Equation.3 1415C.
A13 EMBED Equation.3 1415C, B13 EMBED Equation.3 1415E, D13 EMBED Equation.3 1415A, E13 EMBED Equation.3 1415C.
D13 EMBED Equation.3 1415A, B13 EMBED Equation.3 1415E, A13 EMBED Equation.3 1415E, D13 EMBED Equation.3 1415C, B13 EMBED Equation.3 1415E.
B13 EMBED Equation.3 1415E, A13 EMBED Equation.3 1415D, C13 EMBED Equation.3 1415D, B13 EMBED Equation.3 1415D, E13 EMBED Equation.3 1415A.
A13 EMBED Equation.3 1415B, D13 EMBED Equation.3 1415C, B13 EMBED Equation.3 1415C, E13 EMBED Equation.3 1415D, A13 EMBED Equation.3 1415E.
B13 EMBED Equation.3 1415E, A13 EMBED Equation.3 1415D, C13 EMBED Equation.3 1415D, B13 EMBED Equation.3 1415D, E13 EMBED Equation.3 1415A.
Операции над множествами.
ОПРЕДЕЛЕНИЕ. Объединением двух множеств А и В называется множество, обозна чаемое A13 EMBED Equation.3 1415В и состоящее из тех и только тех элементов, которые принадлежат , хотя бы одному из множеств А или В.
Таким образом: х 13 EMBED Equation.3 1415A13 EMBED Equation.3 1415B 13 EMBED Equation.3 1415 х13 EMBED Equation.3 1415А13 EMBED Equation.3 1415х13 EMBED Equation.3 1415В
ОПРЕДЕЛЕНИЕ. Пересечением двух множеств А и В называется множество, обозна чаемое A13 EMBED Equation.3 1415B и состоящее из всех тех и только тех элементов, которые принад лежат и множеству А и множеству B.
Таким образом: х 13 EMBED Equation.3 1415A13 EMBED Equation.3 1415B 13 EMBED Equation.3 1415 х13 EMBED Equation.3 1415А13 EMBED Equation.3 1415х13 EMBED Equation.3 1415В
ОПРЕДЕЛЕНИЕ. Разностью двух множеств А и В называется множество, обозна чаемое A\В и состоящее из всех тех и только тех элементов, которые принад лежат множеству А и не принадлежат множеству В.
Таким образом: х 13 EMBED Equation.3 1415A\B 13 EMBED Equation.3 1415 х13 EMBED Equation.3 1415А13 EMBED Equation.3 1415х13 EMBED Equation.3 1415В
Очень часто в математике рассматриваются множества, являющиеся подмножества ми некоторого фиксированного множества, которое рассматривается как универ сальное множество: множество R, множество треугольников, четырехугольнике!
ОПРЕДЕЛЕНИЕ. Пусть М - некоторое универсальное множество, А13 EMBED Equation.3 1415М. Дополне нием множества А до М называется множество, обозначаемое A` и состоящее из тех и только тех элементов М, которые не принадлежат А
Таким образом: x13 EMBED Equation.3 1415 A`13 EMBED Equation.3 1415 x13 EMBED Equation.3 1415A другими словами: А`=М\А. Рассмотрим еще одну операцию, которую можно выполнять как над двумя множес твами, так и над любым конечным числом множеств.
ОПРЕДЕЛЕНИЕ. Пусть А и В множества. Декартовым произведением двух множеств А и В называется множество, обозначаемое А13 EMBED Equation.3 1415В и состоящее из всех упорядоченных пар вида (а,в), где а13 EMBED Equation.3 1415А и в13 EMBED Equation.3 1415В.
Таким образом: А13 EMBED Equation.3 1415В={(a,b): а13 EMBED Equation.3 1415А13 EMBED Equation.3 1415 в13 EMBED Equation.3 1415В}
Если А=В, то А13 EMBED Equation.3 1415A называют декартовым квадратом множества А и обозначают А2.
Аналогично определяется декартово произведение n множеств.
A113 EMBED Equation.3 1415A213 EMBED Equation.3 1415А313 EMBED Equation.3 141513 EMBED Equation.3 1415An={( a1,a2,a3,an): ai13 EMBED Equation.3 1415Ai}
Пример:
Пусть A={1,2,3}, B={2,4,6}, тогда A13 EMBED Equation.3 1415B={1,2,3,4,6}, A13 EMBED Equation.3 1415B={2}, A\B={1,3}, B\A={4,6}.
Задания для самостоятельного решения.
14.Найдите множества A13 EMBED Equation.3 1415B, A13 EMBED Equation.3 1415B, A\B, B\A, если
A={3,5,6,7,9}, B={4,6,7,8}
A={3,5,6,7}, B={2,4,8}
A={2,3,4,5,6}, B={3,4,5}
A=Z, B=N
A=R, B=Q
A=Z, B=Q
A=[0;2], B=[1;5]
A=[0;2], B={0,4,6}
15.Перечислите элементы множеств X и Y, если
X\Y={a,b} Y\X={c,d} X13 EMBED Equation.3 1415Y={x,y,z}
X13 EMBED Equation.3 1415Y={a,b,c,d,e} X13 EMBED Equation.3 1415Y={c,d} X\Y={a,e}
X13 EMBED Equation.3 1415Y={a,b,c,d} X 13 EMBED Equation.3 1415Y=Ш X\Y={a}
{X\Y}13 EMBED Equation.3 1415{Y\X}={a,b,c,x,y,z} X 13 EMBED Equation.3 1415Y={d,e,f} X\Y={a,b,c}
ПРЕДИКАТЫ.
Чтобы иметь наглядное представление о том, что такое предикат рассмот рим следующий пример. Возьмем в руки бланк какой-либо справки или, например,
бланк студенческого билета. Даже если на этих бланках есть все необходимые подписи и печати, но не вписано имя того, кому выдана справка или студ.билет, данная справка и студенческий билет документом не являются. Стоит заполнить в них пропуск и вписать фамилию, имя, отчество, как мы сразу получаем документ, Если в бланк студ.билета вписать ФИО того, кто действительно является сту дентом, то получим действительно документ. Если впи шем в него фамилию своего престарелого соседа по дому - то документ получится, но будет поддельным»
Рассмотрим аналогичную ситуацию в математике. Рассмотрим следующие предложения: “x- простое число”, ”x2-3x+2=0”, ”3x+5=0”.
Можно ли назвать эти предложения высказываниями? - Нет. Но если вместо х подставим конкретные числа, то получим высказывания - истинные или ложные. Например, " 14 - простое число" - ложь, "7-простое число" - истина. Однако не любое число, подставленное вместо х обращает эти предложения в высказывания. Например, при X = 3,14 первое предложение принимает вид: "3,14 - простое число". Данное предложение не является высказыванием, так как понятие простое число применимо только в целым числам, а число 3,14 таким не является. Точно также получим, если в бланк студенческого билета вместо ФИО какого-либо человека впишем машина Mersedes-Benz.
ОПРЕДЕЛЕНИЕ. Предикатом о областью определения D(P(x)) (где D(P(x)) - некоторое
множество), называется выражение с переменной P(x), которое превращается в истинное или ложное высказывание, если в него вместо х подставить любой элемент из множества D(P(x)). Множество тех элементов из D(P(x)), при которых предикат превращается в истинное высказывание, называется множеством истинности предиката. Множество истинности предиката Р(х) обозначается следующим образом: {x13 EMBED Equation.3 1415 D(P(x)): P(x)}.
Читается эта запись так: “х из множества D(P(x)), такие что верно Р(х)”.
В дальнейшем будем обозначать множество истинности предиката P(x) как M(P(x)).
ОПРЕДЕЛЕНИЕ. Если множество истинности предиката совпадает с его областью определения, то предикат называется тождественно истинным. Если множество истинности предиката пусто, то предикат называется тождественно ложным.
Примерами предикатов являются уравнения и неравенства с одной переменной. Выражением “x13 EMBED Equation.3 1415D обладает свойством Р” также является предикатом, то есть предикат можно рассматривать как свойство того или иного объекта, при этом множество истинности - это множество объектов, обладающих свойством P.
Равносильность предикатов.
Пусть даны два предиката P(x) и Q(x) и D(P(x))13 EMBED Equation.3 1415D(Q(x))=D.
ОПРЕДЕЛЕНИЕ. Предикат Q(x) называется логическим следствием предиката Р(x), если предикат Q(x) обращается в истинное высказывание при всех тех значениях переменной из множества Д, при которых истинен предикат Р(x), то есть если M(P(x))13 EMBED Equation.3 1415M(Q(x)).
Обозначают это так: Р(х)13 EMBED Equation.3 1415Q(х)
Из определения следует, что если Р(х)13 EMBED Equation.3 1415Q(х), то для любого конкретного х0 верно высказывание P(х0)13 EMBED Equation.3 1415Q(х0).
ОПРЕДЕЛЕНИЕ. Предикаты Р(х) и Q(х) называются равносильными, если предикат Р(х) обращается в истинное высказывания при тех и только тех значениях переменных из множества D, при которых истинен Q(х), то есть если M(P(x))= M(Q(x)).
Обозначают это так : Р(x)13 EMBED Equation.3 1415Q(x).
Из рассмотренных определений следует, что два предиката равносильны тогда и только тогда, когда каждый из них является логическим следствием другого. В частности, из определений следует, что любой предикат является логическим следствием любого тождественно-ложного предиката, Ш 13 EMBED Equation.3 1415 M(P(x)) при любом Р(х)). Все тождественно-истинные предикаты, заданные на одном и том же множестве, равносильны между собой. Все тожественно- ложные предикаты, заданные на одном и том же множестве равносильны между собой.
Задания для самостоятельного решения.
15. Перечислить элементы каждого из следующих множеств.
{x 13 EMBED Equation.3 1415N : x2-x-6=0}
{x 13 EMBED Equation.3 1415Z: x2-413 EMBED Equation.3 14150}
{x 13 EMBED Equation.3 1415R:lg(x+1)=13 EMBED Equation.3 1415}
{n 13 EMBED Equation.3 1415N: 13 EMBED Equation.3 1415}
{q 13 EMBED Equation.3 1415N: 2413 EMBED Equation.3 1415q 13 EMBED Equation.3 1415q13 EMBED Equation.3 14152}
16.При каких a13 EMBED Equation.3 1415R выполнено:
13 EMBED Equation.3 141513 EMBED Equation.3 1415{-1,1,2}
-113 EMBED Equation.3 1415{13 EMBED Equation.3 1415, 2a-1, 13 EMBED Equation.3 1415}
{1,a,a2-1,3}={1,3}
a+1 13 EMBED Equation.3 1415 {1,-1, 13 EMBED Equation.3 1415}
{1,-1,2}13 EMBED Equation.3 1415 {2-a,-1,2,3,13 EMBED Equation.3 1415}
{a,a2,a3}13 EMBED Equation.3 1415[0;27]
{1,-1,3}13 EMBED Equation.3 1415{-a,-3,2a-1,2}
{13 EMBED Equation.3 1415,13 EMBED Equation.3 1415}={a-1,a+1}
17. При каких a количество элементов множества {a,a2,a3}
равно 2
равно 1
18. Пусть Bt=[t-1;t+1], t13 EMBED Equation.3 1415R
при каких t Bt13 EMBED Equation.3 141513 EMBED Equation.3 1415 Ш
при каких t 1013 EMBED Equation.3 1415Bt 13 EMBED Equation.3 1415 10.513 EMBED Equation.3 1415 Bt
при каких x13 EMBED Equation.3 1415R x13 EMBED Equation.3 1415B10 13 EMBED Equation.3 1415 x13 EMBED Equation.3 1415 B10.5
при каких x 13 EMBED Equation.3 1415R x13 EMBED Equation.3 1415B10 13 EMBED Equation.3 1415 x+0.113 EMBED Equation.3 1415 B10
при каких x 13 EMBED Equation.3 1415R x13 EMBED Equation.3 1415B10 13 EMBED Equation.3 1415 x+0.113 EMBED Equation.3 1415B10
Одноместные и многоместные предикаты.
Ранее мы рассмотрели понятие предиката от одной переменной, такие предикаты называются одноместными. Но нам хорошо известны выражения содержащие нес колько переменных, которые превращаются в высказывания при замене этих пере менных конкретными элементами, например системы уравнений, системы неравенств.
ОПРЕДЕЛЕНИЕ. Пусть даны множества A1, A2, Aз,..., Аn. Предикатом Р(x1,xn) с областью определения A113 EMBED Equation.3 1415 A213 EMBED Equation.3 1415 Aз13 EMBED Equation.3 1415...13 EMBED Equation.3 1415Аn называется выражение, содержащее n переменных x1,x2xn, превращающееся в высказывание (истинное или ложное) при подстановке вместо переменных элементов из множеств A1, A2, Aз,..., Аn соот ветственно.
Примеры.
Р(х,у): x-y = 5
Область определения: R2. Множество истинности:M={(x,y)13 EMBED Equation.3 1415R2: y=x-5}
Р(х,у,z): x2+y2 = z2
Область определения: R3.
Множество истинности:M={(x,y,z)13 EMBED Equation.3 1415R3: x2+y2=z2}
Операции над предикатами.
При конкретных значениях переменных предикаты как и высказывания принимают
значения "истина" и "ложь", поэтому над ними можно производить логические
операции.
Пусть Р(х) и Q (х) два одноместных предиката от одной и той же перемен ной такие, что
DP(x)13 EMBED Equation.3 1415D; DQ(x)13 EMBED Equation.3 1415D.
ОПРЕДЕЛЕНИЕ. Отрицанием предиката Р(х) называется новый предикат, обозна чаемый13 EMBED Equation.3 1415P(x), определенный на том же множестве, который принимает значение истины при тех значениях переменной, при которых Р(х) принимает значение ложь и наоборот. Таким образом, M13 EMBED Equation.3 1415P(x)=DP(x)\MP(x)
ОПРЕДЕЛЕНИЕ. Конъюнкцией предикатов Р(х) и Q(х) называется новый предикат, обозначаемый Р(х)13 EMBED Equation.3 1415Q(х), заданный на DP(x)13 EMBED Equation.3 1415DQ(x) , который обращается в истинное высказывание для тех и только тех значений переменной, для которых ис тины оба предиката Р(х) и Q(х). Таким образом, MP(x)13 EMBED Equation.3 1415Q(x)=MP(x)13 EMBED Equation.3 1415MQ(x)
Пример: 13 EMBED Equation.3 1415 - конъюнкция предикатов
ОПРЕДЕЛЕНИЕ. Дизъюнкцией двух предикатов Р(х) и Q(х) называется новый пре дикат, обозначаемый P(x)13 EMBED Equation.3 1415Q(x), заданный на DP(x)13 EMBED Equation.3 1415DQ(x), который превращается в истинное высказывание для тех и только тех значений переменных, для которых истинен хотя бы один из предикатов Р(х) или Q(х).Таким образом MP(x)13 EMBED Equation.3 1415Q(x)=MP(x)13 EMBED Equation.3 1415MQ(x)
Пример:13 EMBED Equation.3 1415 - дизъюнкция предикатов
ОПРЕДЕЛЕНИЕ. Импликацией предикатов Р(х) и Q(х) называется новый предикат, который обозначается P(x)13 EMBED Equation.3 1415Q(x), заданный на DP(x)13 EMBED Equation.3 1415DQ(x), который превращается в ложное высказывание для тех и только тех значений переменной для которых P(x)- истинен, а Q(х) – ложен. Таким образом MP(x)13 EMBED Equation.3 1415 Q(x)=M13 EMBED Equation.3 1415P(x)13 EMBED Equation.3 1415MQ(x)
Аналогичным образом можно дать определения логических операций для многоместных предикатов.
Пример: 13 EMBED Equation.3 1415 - конъюнкция двух двухместных предикатов
КВАНТОРЫ.
Рассмотрим для начала одноместный предикат: Р(х): х - четное число.
D(P(x)) - множество целых чисел. Прочитаем следующие выражения:
Р(8) :"8 - четное число"
Р(7) :" 7 - четное число"
Для всех х Р(х):"Любое целое число x - четное"
Для некоторых х P(x): "Некоторые целые числа х - четные"
Предложение 1 - истинное высказывание, предложение 2 - ложное высказывание. Эти высказывания получены заменой в предикате переменной х конкретными числами. Предложения 3 и 4 - тоже высказывания, 3 - ложное, 4 - истинное. Но получены эти высказывания из предиката не заменой переменной конкретным числом, а употреблением выражений "для всех х" и "для некоторых х".
ОПРЕДЕЛЕНИЕ. Операция превращения предиката в высказывание с помощью приписывания квантора называется квантификацией (или "навешиванием кванторов"). Рассматриваются два квантора: квантор всеобщности и квантор существования. Квантор всеобщности обозначается перевернутой буквой А: 13 EMBED Equation.3 1415 (от англий ского слова All - все. Квантор существования обозначается перевернутой буквой Е: 13 EMBED Equation.3 1415 от (от английского слова Exist – существовать).
Высказывания, полученные с помощью приписывания квантора, обозначают так:
13 EMBED Equation.3 1415х13 EMBED Equation.3 1415D: Р(х) - читают "Для любого х из D: Р(х)
13 EMBED Equation.3 1415 х13 EMBED Equation.3 1415D: Р(х) - читают "Существует х из D, такое, что Р(х)"
Если понятно, из какого множества берут элемент х, то пишут просто: 13 EMBED Equation.3 1415х: Р(х) 13 EMBED Equation.3 1415 х: Р(х)
Еcли мы имеем n -местный предикат, то кванторы можно" навесить" либо на все переменные, либо на часть из них. Переменная, на которую "навешан" квантор, называется связанной, а остальные переменные называются свободными. Если все переменные связаны, то предикат перестает быть предикатом и становится высказыванием (истинным или ложным). Если некоторые переменные связаны, а часть переменных осталась свободной, то получаем предикат о меньшим числом переменных. Например: 13 EMBED Equation.3 1415x13 EMBED Equation.3 1415R13 EMBED Equation.3 1415x13 EMBED Equation.3 1415R - истинное высказывание;
13 EMBED Equation.3 1415x13 EMBED Equation.3 1415Z x + y 13 EMBED Equation.3 1415 5 - одноместный предикат от y;
Для того, чтобы определить истинно или ложно высказывание с кванторами вос пользуемся определениями. (Все определения рассмотрим только для одноместных предикатов для того, чтобы облегчить запись).
ОПРЕДЕЛЕНИЕ. Высказывание 13 EMBED Equation.3 1415х13 EMBED Equation.3 1415D: Р(х) является истинным тогда и только, когда множество истинности предиката Р(х) совпадает с его областью определения то есть, если Р(х) - тождественно истинный предикат.
Пример : 13 EMBED Equation.3 1415x13 EMBED Equation.3 1415R x2+1>0 - истинное высказывание.
Из определения следует, что высказывание 13 EMBED Equation.3 1415х: Р(х) ложно тогда и только
тогда, когда при некотором х013 EMBED Equation.3 1415D высказывание P(x0) - ложно.
ОПРЕДЕЛЕНИЕ. Элемент х013 EMBED Equation.3 1415D, для которого P(x0) – ложно, называется контр-
примером для высказывания13 EMBED Equation.3 1415х: Р(х).
Примеры: 13 EMBED Equation.3 1415x13 EMBED Equation.3 1415R x2+3x-2>0 – ложь, так как при x0=О x02+3x0-2 < 0; x0 =0 – контрпример;
ОПРЕДЕЛЕНИЕ. Высказывание 13 EMBED Equation.3 1415 х13 EMBED Equation.3 1415D: Р(х) является истинным тогда и только
тогда, когда множество истинности предиката Р(х) не пусто: M(P(X))13 EMBED Equation.3 1415 Ш, то
есть Р(х) не является тождественно ложным предикатом.
Из определения следует, что для того, чтобы доказать, что высказывание с
квантором существования истинно достаточно предъявить элемент из множества
D, при котором Р(х) будет истинно.
Примеры: 13 EMBED Equation.3 1415 х13 EMBED Equation.3 1415R: x2-1=0 - истина, так как 113 EMBED Equation.3 1415 M(P(X)), то есть M(P(X))13 EMBED Equation.3 1415 Ш
13 EMBED Equation.3 1415 х13 EMBED Equation.3 1415R: x2-x+100=0 - ложь, так как M(P(X))13 EMBED Equation.3 1415 Ш
Следует отметить важный факт: при рассмотрении высказываний с кванторами полученных из предикатов от нескольких переменных, смысл высказываний су щественно зависит от того в каком порядке записаны кванторы и переменные к которым они относятся. Рассмотрим это на примере.
Пусть Р(х,у) - эти предикат: "официант х обслуживает стол уи. Тогда прочи таем следующие высказывания:
13 EMBED Equation.3 1415x13 EMBED Equation.3 1415y P(x,y) - каждый официант имеет стол, который он обслуживает;
13 EMBED Equation.3 1415y13 EMBED Equation.3 1415y Р(х,у) - для каждого стола есть официант, который его обслуживает;
13 EMBED Equation.3 1415y13 EMBED Equation.3 1415x Р(х,у) - существует стол, который обслуживается любым официантом;
13 EMBED Equation.3 1415x13 EMBED Equation.3 1415y Р(х,у) - существует официант, который обслуживает любой стол.
Задания для самостоятельного решения.
19. Определить истины или ложны высказывания на множестве R.
13 EMBED Equation.3 1415x13 EMBED Equation.3 1415y x+y=7
13 EMBED Equation.3 1415y13 EMBED Equation.3 1415x x+y=7
13 EMBED Equation.3 1415x 13 EMBED Equation.3 1415y x+y=7
13 EMBED Equation.3 1415y13 EMBED Equation.3 1415y x+y=7
13 EMBED Equation.3 1415x13 EMBED Equation.3 1415y y>x
13 EMBED Equation.3 1415y13 EMBED Equation.3 1415x y>x
Кванторы существования и всеобщности постоянно употребляются и в математических текстах и в обычной речи, но выражено это может быть разными словами. Надо научиться "видеть" кванторы, предикаты и переменные в любых высказываниях.
20.Записать следующие фразы на языке предикатов и кванторов.
Bce рыбы плавают.
Ни одна собака не умеет мяукать
Кто хочет, тот добьется
Если кто-нибудь может прыгнуть в окно, то и Вася может
Либо каждый любит кого-нибудь и ни один не любит всех, либо некто любит всех и кто-то не любит никого.
Отрицание высказываний с кванторами.
Для того, что бы способ построения высказываний, содержащий отрицание и кванторы
стал более наглядным, рассмотрим примеры.
Произнести следующие предложения, не употребляя слова "неправда”:
1. Неправда, что все рыбы плавают.
2. Неправда, что некоторые реки впадают в Каспийское море.
Совершенно очевидно, что в русском языке вместо предложения 1 мы скажем: "есть рыбы, которые не умеют плавать", а вместо предложения 2 - "каждая река не впадает в Каспийское море". Эти примеры показывают, что справедливы следующие формулы:
13 EMBED Equation.3 1415(13 EMBED Equation.3 1415x Р(х)) 13 EMBED Equation.3 1415x (13 EMBED Equation.3 1415 P(x)) (1)
13 EMBED Equation.3 1415(13 EMBED Equation.3 1415x Р(х)) 13 EMBED Equation.3 1415x (13 EMBED Equation.3 1415 P(x)) (2)
Доказательство:
13 EMBED Equation.3 1415(13 EMBED Equation.3 1415x Р(х)) = Л 13 EMBED Equation.3 141513 EMBED Equation.3 1415x Р(х) = И 13 EMBED Equation.3 1415 M(P(x))=D 13 EMBED Equation.3 1415 M(13 EMBED Equation.3 1415P(x))=Ш 13 EMBED Equation.3 141513 EMBED Equation.3 1415x (13 EMBED Equation.3 1415 P(x))=Л
13 EMBED Equation.3 1415(13 EMBED Equation.3 1415x Р(х)) = И 13 EMBED Equation.3 141513 EMBED Equation.3 1415x Р(х) = Л 13 EMBED Equation.3 1415 M(P(x))= Ш 13 EMBED Equation.3 1415 M(13 EMBED Equation.3 1415P(x))=D\ Ш 13 EMBED Equation.3 141513 EMBED Equation.3 1415x (13 EMBED Equation.3 1415 P(x))=И
Задания для самостоятельного решения.:
21.13 EMBED Equation.3 1415(13 EMBED Equation.3 1415x13 EMBED Equation.3 1415y P(x,y)) 13 EMBED Equation.3 1415x13 EMBED Equation.3 1415(13 EMBED Equation.3 1415y P(x,y)) 13 EMBED Equation.3 1415x13 EMBED Equation.3 1415y13 EMBED Equation.3 1415 P(x)
22.Произнести предложение, не употребляя слово "неправда":
"Неправда, что некотором поезде, идущем из Санкт-Петербурга в Москву, в каждом вагоне есть свободное место".
В каждом поезде, идущем из Санкт-Петербурга в Москву существует вагон, в котором все места заняты".
23.Пусть П(х) - x - простое число;
Ч(х) - х - четное число;
Н(х) - х -нечетное числе;
Д(х,у) - y делится на х ;
Прочитать и построить отрицание к формуле:
(13 EMBED Equation.3 1415x (Ч(x)13 EMBED Equation.3 1415 (13 EMBED Equation.3 1415y Д(x,y) 13 EMBED Equation.3 1415Ч(y))
Root EntryEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Native