Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Свидетельство о публикации

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Информатика / Другие методич. материалы / Методическая разработка «ОСНОВНЫЕ ПОНЯТИЯ МАТЕМАТИЧЕСКОЙ ЛОГИКИ»
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 28 июня.

Подать заявку на курс
  • Информатика

Методическая разработка «ОСНОВНЫЕ ПОНЯТИЯ МАТЕМАТИЧЕСКОЙ ЛОГИКИ»

библиотека
материалов


Государственное бюджетное общеобразовательное
учреждение лицей № 393 Кировского района Санкт-Петербурга












МЕТОДИЧЕСКАЯ РАЗРАБОТКА


«ОСНОВНЫЕ ПОНЯТИЯ МАТЕМАТИЧЕСКОЙ ЛОГИКИ»






Подготовил

учитель информатики

Смирнов Игорь Александрович










г. Санкт-Петербург
2016









ВЫСКАЗЫВАНИЯ И ЛОГИЧЕСКИЕ ОПЕРАЦИИ НАД НИМИ


ОПРЕДЕЛЕНИЕ. Высказывание - это повествовательное предложение о котором можно сказать однозначно истинно оно или ложно.


Задание: Какие из следующих предложении являются высказываниями?


1. Стой! Куда идёшь?

2. Нева впадает в Черное море.

3. Да здравствуют учащиеся школы № 139!

4. A > 0

5. 2+ hello_html_2d077f92.gif

6. 15 - простое число

  1. 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 = Л означает, что высказывание А - ложно.

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


ОПРЕДЕЛЕНИЕ. Отрицанием высказывания А называется новое высказывание, обозначаемое hello_html_m382c1dc9.gifhello_html_m62170625.gif ( или hello_html_m26dae56d.gif ), читаемое "неверно, что А" или короче "не А", которое истинно, если А ложно, и ложно, если А истинно.

Зависимость значения истинности высказывания А от значения истинности высказывания А можно выразить с помощью таблицы, называемой таблицей

истинности .

Таблица истинности отрицания.

hello_html_m382c1dc9.gifhello_html_m62170625.gif

И

Л

Л

И


Пример: hello_html_m62170625.gif= ”2 - простое число

hello_html_m382c1dc9.gifhello_html_m62170625.gif - "2 не является простым числом” или "неверно, что 2 — простое число".


ОПРЕДЕЛЕНИЕ: Конъюнкцией двух высказываний А к В называется новое высказывание, которое обозначается A hello_html_3af2f246.gif B ( или A & B ) , читается "A и В” и которое истинно, если истины оба высказывания А и В и ложно во всех остальных случаях.

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

Название конъюнкция происходит от английского слова conjunction

  • соединение, совпадение.


Пример: Прогноз погоды на завтра "завтра по области будет дождь и температура понизится до 10°". Логично считать прогноз оправданным, если и дождь будет и температура понизится, и неправильным во всех остальных случаях.


Таблица истинности конъюнкции:

A

B

A hello_html_3af2f246.gif B

И

И

И

И

Л

Л

Л

И

Л

Л

Л

Л


Задание: Определить истинны ли следующие высказывания:

1.Санкт-Петербург расположен на Неве и 9 - простое число

Иhello_html_3af2f246.gifЛ=Л

2. 2*2=4 и снег – белый

Иhello_html_3af2f246.gifИ=И

3. 2*2=5 и 48hello_html_3321970c.gif5

Лhello_html_3af2f246.gifЛ=Л


В школе вы неоднократно встречались с конъюнкцией и привыкли для ее обозначения использовать знак системы: 4<7< 9 это конъюнкция двух высказываний. Это можно записать: (4 < 7) hello_html_3af2f246.gif (7 < 9) или hello_html_7ed5d3e7.gif.

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

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

Пример: Студенты готовятся к экзамену по учебникам или по конспектам. Сегодня в 19 часов я пойду в кино или в театр. И первом случае подготовка к экзамену по конспектам не исключает использования учебника и наоборот. Во втором случае может быть верна лишь одна возможность; театр или кино.


ОПРЕДЕЛЕНИЕ: Дизъюнкцией высказываний А и В называется новое высказывая которое обозначается А hello_html_709f5f78.gifB, читается “А или В” и которое истинно, если истинно хотя бы одно из высказываний А и B и ложно, если оба высказывания ложны. Операцию дизъюнкция иногда называют логическим сложением, а высказывания А и В - членами дизъюнкции или слагаемыми.

Название дизъюнкция происходит от английского олова disjunction - разъединение, разобщение.


Пример: 2x2=4 или белые медведи живут в Африке – истинно. Из определения видно, что союз или используется в неисключающем смысле. Число 2 - четное или 2 – нечетное. – истинно.



Таблица истинности дизъюнкции:


A

B

A hello_html_709f5f78.gif B

И

И

И

И

Л

И

Л

И

И

Л

Л

Л


В школе вы так же встречались с дизъюнкцией: 2hello_html_3813d461.gif2 - это дизъюнкция двух высказываний 2<2 и 2 = 2, 7hello_html_3813d461.gif3 - это дизъюнкция двух высказываний 7<3 и 7=3.

Для записи дизъюнкции используют также знак “совокупности” hello_html_m115766e.gif

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

"Отец оказал сыну: Если я получу премию, то я куплю тебе велосипед”. Обозначим: А – “я получу премию”, В –“я куплю тебе велосипед”. Тогда обещание отца запишем так: Аhello_html_m6bb904b4.gifВ. Еcли ребенок будет считать, что отец одержал слово, то высказывание Аhello_html_m6bb904b4.gifВ целесообразно считать истинным, если нет, - ложным.

Рассмотрим варианты:

  1. Получена премия, куплен велосипед - слово сдержано.

  2. Не получена премия и не куплен велосипед - cлово сдержано.

  3. Не получена премия, но велосипед куплен - поступок отца не является нарушением обещания.

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


ОПРЕДЕЛЕНИЕ. Импликацией двух высказываний А и В называется новое высказывание обозначаемое Аhello_html_m6bb904b4.gifВ, читается “если А, то В” или “из А следует В”, которое ложно лишь в одном случае: когда А истинно, а В ложно и истинно во всех остальных случаях. Высказывание А называется условием или посылкой а высказывание В - заключением или следствием.

Название импликация происходит от английского слова implication - вовлечение, заключение в себя.


Таблица истинности импликации.


A

B

A hello_html_m6bb904b4.gif B

И

И

И

И

Л

Л

Л

И

И

Л

Л

И


Задание: Определить истинны ли следующие высказывания

Если 2*2=5, то снег черный.

Лhello_html_m6bb904b4.gifЛ=И

Если 2*2=5, то 6 делится на 3.

Лhello_html_m6bb904b4.gifИ=И

Если 2 меньше 3, то 3 меньше нуля.

Лhello_html_m6bb904b4.gifЛ=И


В обычной речи мы привыкли, что слова “из А следует B“ предполагает, что между А и В существует некая зависи­мость, в силу которой высказывание А может быть как-то получено из В. Тогда первый пример есть высказывание не имеющее смысла. Но определение импликации позволяет рассматривать импликацию двух любых высказываний и определять логическое значение такой импликации. Значение импликации для математических доказательств состоит в том, что из истинности импликации и её посылки мы можем сделать вывод об истинности её заключения.


Задание: пусть истинна импликация: “Еcли 4 - четное числе, то А. Каково логическое значение высказывания А?

Иhello_html_m6bb904b4.gifA=И, тогда А=И


ОПРЕДЕЛЕНИЕ. Эквивалентностью двух высказываний А и B называется новое высказывание обозначаемое А hello_html_m57fecaf3.gifВ, читается "А эквивалентно B” или "А равносильно B” или "А тогда и только тогда, когда B”, которое считается истинным, если А и В одновременно оба истинны или оба ложны, а в остальных случаях ложно. А и В называются членами эквивалентности. Название эквивалентность происходит от английского слова equivalence - равноценность, эквивалентность.


Таблица истинности эквивалентности.


A

B

A hello_html_m57fecaf3.gif B

И

И

И

И

Л

Л

Л

И

Л

Л

Л

И


Примеры:

Натуральное число n делится на 3 тогда и только тогда когда сумма его цифр делится на 3. - истина

2=3 тогда и только тогда, когда 5 больше 6. - истина


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


Задания для самостоятельного решения:


  1. Определите истинностное значение высказываний:

  1. Если 12 делится на 6 , то 12 делится на 3.

  2. Если 11 делится на 6 , то 11 делится на 3.

  3. Если 15 делится на 6 , то 15 делится на 3.

  4. Если 15 делится на 3 , то 15 делится на 6.

  5. 12 делится на 6, тогда и только тогда, когда 12 делится на 3.

  6. 11 делится на 6, тогда и только тогда, когда 11 делится на 3.

  7. 15 делится на 6, тогда и только тогда, когда 15 делится на 3.


2. Каково истинностное значение высказывания А, если истинно высказывание:

  1. А и 2*2=4

  2. А или 2*2=5

  3. Если А, то 4 - нечетное число

  4. Если 3>2, то 6hello_html_3321970c.gif2 и А

  5. Если 13hello_html_47aa72e7.gif13 и А, то 4 >7

  6. Если 12hello_html_3321970c.gif3, то А или 3hello_html_3321970c.gif2

  7. Если А или 6hello_html_3321970c.gif2, то 8hello_html_3321970c.gif2 и A


3.Каково истинностное значение высказывания А, если ложно высказы­вание:

  1. A и 2*2=4

  2. А или 2*2=5

  3. А и 2*2=5

  4. Еcли 2 - четно, то А

  5. Еcли А, то 4 - нечетное число

  6. Если А или 6hello_html_3321970c.gif3, то 8hello_html_47aa72e7.gif10 и А

  7. Если 6 > 7 и А, то 12hello_html_3321970c.gif4 и А

  8. Если 4hello_html_3321970c.gif2 и А, то 12> 2 и А


4.Найдите истинностные значения высказываний

  1. ((22<4)hello_html_709f5f78.gif(7>5)hello_html_m6bb904b4.gifhello_html_m382c1dc9.gif(5>9)

  2. hello_html_m382c1dc9.gif(33=27) hello_html_709f5f78.gif ((2>7)hello_html_3af2f246.gif(6=5))

  3. (7*7=49) hello_html_3af2f246.gif (3*3=2) hello_html_709f5f78.gif (23=7))

  4. hello_html_m382c1dc9.gif((2*2=5)hello_html_3af2f246.gif(3*3=7)

  5. hello_html_m382c1dc9.gif(2*2=3)hello_html_m6bb904b4.gif((3=4)hello_html_m6bb904b4.gif(2>7))


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, их значения совпадут). Таким образом, и в числовых и в алгебраичес­ких выражениях скобки играют существенную роль. Если скобки не поставлены и нет никаких договоренностей о последовательности выполнения основных действий, то на самом деле просто нельзя вычислить значение ни одного алгебраического выражения.

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

Например, запись Аhello_html_m6bb904b4.gifВhello_html_m6bb904b4.gifС - не является логической формулой, так как не ясна последовательность выполнения логической операции импликация. Выражения (Аhello_html_m6bb904b4.gifВ)hello_html_m6bb904b4.gifС и Аhello_html_m6bb904b4.gifhello_html_m6bb904b4.gifС) - являются логическими формулами. Видно, что это разные высказывания, так как при одинаковых значе­ниях входящих в формулу логических переменных А,В, С они могут принимать разные логические значения. Например, если A=B=C=Л, то (Аhello_html_m6bb904b4.gifВ)hello_html_m6bb904b4.gifС =Л, а Аhello_html_m6bb904b4.gifhello_html_m6bb904b4.gifС)=И.

Задание: Вычислить логическое значение формул при A = И, B = С= Л

a) (Аhello_html_709f5f78.gifВ) hello_html_m6bb904b4.gifhello_html_3af2f246.gifВ)

hello_html_709f5f78.gifЛ) =И; (Л hello_html_3af2f246.gifЛ)=Л; (Иhello_html_m6bb904b4.gifЛ) =Л;

b) (Ahello_html_709f5f78.gif( В hello_html_m6bb904b4.gifС) hello_html_3af2f246.gifB)

hello_html_m6bb904b4.gifЛ)=И; (Иhello_html_709f5f78.gifИ)=И; (Иhello_html_3af2f246.gifЛ)=Л;

c) Ahello_html_709f5f78.gif((Bhello_html_m6bb904b4.gifC)hello_html_3af2f246.gifB)

Лhello_html_m6bb904b4.gifЛ=Л; (Лhello_html_3af2f246.gifЛ)=Л; (Иhello_html_709f5f78.gifЛ)=И;


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


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

a) Если мы поедем летом в Париж и у нас будет достаточно времени, то мы посетим Лувр.

A- мы поедем летом в Париж; B- у нас будет время; C- мы посетим Лувр;

Ahello_html_3af2f246.gifBhello_html_m6bb904b4.gifC

b) Если мы скоро окончим работу и будет хорошая погода, то мы пойдем на про­гулку или поедем на пляж.

A- скоро окончим работу; B- будет хорошая погода; C- пойдем на про­гулку; D- поедем на пляж;

(Ahello_html_3af2f246.gifB) hello_html_m6bb904b4.gif(Chello_html_709f5f78.gifD)

c) Если мистер Смиттенгольдц счастлив, то миссис Смиттенгольдц несчастлива, и если мистер Смиттенгольдц несчастлив, то миссис Смиттенгольдц счастлива.

A- мистер Смиттенгольдц счастлив; B- миссис Смиттенгольдц счастлива;

(Ahello_html_m6bb904b4.gifhello_html_m382c1dc9.gifB) hello_html_3af2f246.gif(hello_html_m382c1dc9.gifAhello_html_m6bb904b4.gifB)

d) Если летом будет дождливая погода, то ни накупаться нам не удастся, ни загорать нам не удастся.

A- будет дождливая погода;B- удастся накупаться; C- удастся загорать;

A hello_html_m6bb904b4.gif (hello_html_m382c1dc9.gifBhello_html_3af2f246.gifhello_html_m382c1dc9.gifC)



Равносильные формулы.


Запишем на языке логических формул два сложных высказывания.

1. Неверно, что завтра будет дождь и температура воздуха понизится до 100

2. 3автра не будет дождя или температура не понизится до 10°

Одна и та же информация заключена в этих двух высказываниях или нет?

Попробуем рассмотреть это формально. Обозначим: А -"завтра будет дождь"; В - "завтра температура воздуха понизится до 100".

Тогда высказывания примут вид: F1=hello_html_m382c1dc9.gif(Ahello_html_3af2f246.gifB) и F2=hello_html_m382c1dc9.gifAhello_html_709f5f78.gifhello_html_m382c1dc9.gifB

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

A

B

hello_html_m382c1dc9.gif(Ahello_html_3af2f246.gifB)

hello_html_m382c1dc9.gifAhello_html_709f5f78.gifhello_html_m382c1dc9.gifB

И

И

Л

Л

И

Л

И

И

Л

И

И

И

Л

Л

И

И


И по смыслу и по таблицам видно, что эти формулы выражают одно и тоже содержание.


ОПРЕДЕЛЕНИЕ. Пусть даны две логические формулы, содержание одни и те же переменные A1,A2,A3,…An. Формулы называются равносильными, если при любых логических значениях переменных A1,A2,A3,…An логические значения данных формул совпадают.

Для обозначения равносильности формул можно использовать значки hello_html_65afd3a0.gif или hello_html_m739d14ab.gif.

В нашем примере мы доказали, что рассматриваемые нами формулы равносильны, то есть

F1 (A1,A2,A3,…An ) hello_html_65afd3a0.gifF2(A1,A2,A3,…An )

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


Рассмотрим основные пары равносильных формул.

  • закон двойного отрицания hello_html_m382c1dc9.gif(hello_html_m382c1dc9.gifA)hello_html_65afd3a0.gifA

  • законы Моргана hello_html_m382c1dc9.gif(Ahello_html_709f5f78.gifB)hello_html_65afd3a0.gifhello_html_m382c1dc9.gifAhello_html_3af2f246.gifhello_html_m382c1dc9.gifB

  • hello_html_m382c1dc9.gif(Ahello_html_3af2f246.gifB)hello_html_65afd3a0.gifhello_html_m382c1dc9.gifAhello_html_709f5f78.gifhello_html_m382c1dc9.gifB

  • законы идемпотентности Ahello_html_709f5f78.gifAhello_html_65afd3a0.gifA

  • Ahello_html_3af2f246.gifAhello_html_65afd3a0.gifA

  • законы коммутативности Ahello_html_3af2f246.gifBhello_html_65afd3a0.gifBhello_html_3af2f246.gifA

  • Ahello_html_709f5f78.gifBhello_html_65afd3a0.gifBhello_html_709f5f78.gifA

  • законы ассоциативности (Ahello_html_3af2f246.gifB)hello_html_709f5f78.gifChello_html_65afd3a0.gif(Ahello_html_709f5f78.gifC)hello_html_3af2f246.gif(Bhello_html_709f5f78.gifC) (Ahello_html_709f5f78.gifB)hello_html_3af2f246.gifChello_html_65afd3a0.gif(Ahello_html_3af2f246.gifC)hello_html_709f5f78.gif(Bhello_html_3af2f246.gifC)

  • законы дистрибутивности Ahello_html_3af2f246.gif(Bhello_html_709f5f78.gifC) hello_html_65afd3a0.gif(Ahello_html_3af2f246.gifB)hello_html_709f5f78.gif(Ahello_html_3af2f246.gifC)

  • Ahello_html_709f5f78.gif(Bhello_html_3af2f246.gifC) hello_html_65afd3a0.gif(Ahello_html_709f5f78.gifB)hello_html_3af2f246.gif(Ahello_html_709f5f78.gifC)

  • законы поглощения Ahello_html_709f5f78.gif(Bhello_html_3af2f246.gifA) hello_html_65afd3a0.gifA

  • Ahello_html_3af2f246.gif(B hello_html_709f5f78.gifA) hello_html_65afd3a0.gifA

  • Ahello_html_709f5f78.gifИ hello_html_65afd3a0.gif И

  • Ahello_html_709f5f78.gifЛ hello_html_65afd3a0.gifA

  • Ahello_html_3af2f246.gifИ hello_html_65afd3a0.gifA

  • Ahello_html_3af2f246.gifЛ hello_html_65afd3a0.gif Л

  • A hello_html_m6bb904b4.gifB hello_html_65afd3a0.gif hello_html_m382c1dc9.gifA hello_html_709f5f78.gifB

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

Задание. На занятиях по математической логике студентам было предложено запи­сать с помощью логических операций и простых высказываний следующее высказы­вание: "Если сегодня не выходной, то Коля идет в школу, если у него нет вы­сокой температуры”. Студенты ввели обозначения для простых высказываний: А - сегодня выходной день, В - Коля идет в школу, С - у Коли нет высокой тем­пературы. Два студента составили различные формула, соответствующие данному высказыванию:

1) hello_html_m382c1dc9.gifAhello_html_m6bb904b4.gif(Chello_html_m6bb904b4.gifB) 2)(hello_html_m382c1dc9.gifAhello_html_3af2f246.gifC)hello_html_m6bb904b4.gifB

Доказать, что данные формулы равносильны.

Первый способ:

hello_html_m382c1dc9.gifAhello_html_m6bb904b4.gif(Chello_html_m6bb904b4.gifB) hello_html_65afd3a0.gif hello_html_m382c1dc9.gif(hello_html_m382c1dc9.gifA)hello_html_709f5f78.gif(hello_html_m382c1dc9.gifChello_html_709f5f78.gifB) hello_html_65afd3a0.gif hello_html_m382c1dc9.gifAhello_html_3af2f246.gifC hello_html_709f5f78.gifB

(hello_html_m382c1dc9.gifAhello_html_3af2f246.gifC)hello_html_m6bb904b4.gifB hello_html_65afd3a0.gif(hello_html_m382c1dc9.gif(hello_html_m382c1dc9.gifAhello_html_3af2f246.gifC))hello_html_709f5f78.gifB hello_html_65afd3a0.gif hello_html_m382c1dc9.gifAhello_html_3af2f246.gifC hello_html_709f5f78.gifB

Мы видим, что обе формулы равносильны одной и той же третьей формуле, а значит, равносильны между собой.

Второй способ.

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


A

B

C

hello_html_m382c1dc9.gifAhello_html_m6bb904b4.gif(Chello_html_m6bb904b4.gifB)

(hello_html_m382c1dc9.gifAhello_html_3af2f246.gifC)hello_html_m6bb904b4.gifB

И

И

И

И

И

И

И

Л

И

И

И

Л

И

И

И

И

Л

Л

И

И

Л

И

И

И

И

Л

И

Л

И

И

Л

Л

И

Л

Л

Л

Л

Л

И

И

Видим, что таблицы истинности формул совпадают, значит формулы равносильны.


Задания для самостоятельного решения:

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

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

  2. Если бы Платон был в Египте и видел там пирамиды, то они бы его очень заинтере­совали, или если бы кто-нибудь обратил на них его внимание, и ему было бы объяснено их устройство, то они могли бы произвести на него неизгладимое впечатление.

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

  4. Если "Спартак" и "Локомотив " проиграют, а "Зенит" выиграет, то "ЦСКА" по­теряет первое место, а на третье место выйдет "Торпедо


8. Упростить формулы.

  1. hello_html_m382c1dc9.gif(hello_html_m382c1dc9.gifAhello_html_3af2f246.gifhello_html_m382c1dc9.gifB)hello_html_709f5f78.gif((Ahello_html_m6bb904b4.gifB)hello_html_3af2f246.gifA)

  2. (Ahello_html_m6bb904b4.gifB)hello_html_3af2f246.gif(Bhello_html_m6bb904b4.gifA)hello_html_3af2f246.gif(Ahello_html_709f5f78.gifB)

  3. (Ahello_html_m6bb904b4.gifB)hello_html_3af2f246.gif(Bhello_html_m6bb904b4.gifhello_html_m382c1dc9.gifA)hello_html_3af2f246.gif(Chello_html_m6bb904b4.gifA)

  4. hello_html_m382c1dc9.gif((Ahello_html_m6bb904b4.gifB)hello_html_3af2f246.gif(Bhello_html_m6bb904b4.gifhello_html_m382c1dc9.gifA))


9. При составлении расписания уроков учителя истории, математики и литературы попросили завуча поставить им их уроки в среду: математи­ку - первым или вторым, историю - первым или третьим; литературу - вторым или третьим. Как используя средства математической логики сос­тавить расписание на среду учитывая все пожелания.

Указание: При решении введем следующие обозначения:

Mi - математика стоит i-м уроком

Иi - история стоит i-м уроком

Лi - литература стоит i-м уроком


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

Указание: При решении введем следующие обозначения:

A - прочитал не менее двух книг

B - сходил в театр

C - сходил на концерт

D - выпал снег

E - съездил на лыжную прогулку

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

« В школе должно быть выполнено одно из условий:

    1. инспектору не разрешается курить в школе

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

    3. ученики должны быть предупреждены об этом или учителя должны принять меры для быстрого уничтожения окурков

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

Как используя средства математической логики упростить директиву директора?



МНОЖЕСТВА.


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

Предметы, из которых состоит множество ,называют его элементами. Если эле­мент а входит в множество А, то говорят, что элемент а принадлежит множеству А и обозначают: аhello_html_m7cb53dec.gifА. Если элемент а не входит в множество А, то пишут аhello_html_m69d35eb5.gif А. Заметим: для любых конкретных а и А: аhello_html_m7cb53dec.gifА - это высказывание, истинное или ложное.

Пример:

В.В.Путин hello_html_m7cb53dec.gif множеству учеников школы № 139

Ученица Пышкина hello_html_m7cb53dec.gif множеству президентов США;

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

Примеры. Русский алфавит: А,Б,В,Г,Д,..., Э,Ю,Я

1,2,3,4,… - множество натуральных чисел

Множество произведений А.C.Пушкина

Множество студентов

Множество окон в кабинете №38 школы №139

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

Русское слово "множество” может ввести в заблуждение. Оно предполагает не­которое изобилие. Однако математическое понятие "множество" этого оттенка может не иметь. Оно может состоять из одного-двух элементов.

Например, множество корней уравнения x2-3x+2 = 0 состоит из двух элементов 1,2. Множество корней уравнения 3x-6=0 - из одного элемента - 2.

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

Примеры: hello_html_m53d4ecad.gifМножество квадратных колес, множество вечных двигателей,

множество вещест­венных корней уравнения 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] - множество всех вещественных чисел: аhello_html_3813d461.gifxhello_html_3813d461.gifb

[a,b) - множество всех вещественных чисел: аhello_html_3813d461.gifx<b

(a,b) - множество всех вещественных чисел: а<x<b

(a,b] - множество всех вещественных чисел: а<xhello_html_3813d461.gifb

(-hello_html_m62eac1ed.gif,b] - множество всех вещественных чисел: xhello_html_3813d461.gifb

(a, hello_html_m62eac1ed.gif] - множество всех вещественных чисел: а<x


Подмножества.


Рассмотрим слово МНОЖЕСТВА как совокупность букв, из которых оно состоит

{ м, н, о, ж , е, с, т, в, o}

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

{н,о,ж},{н,о,с},{с,о,н},{ж,е,н,а},{ж,е,т,о,н},{м,а,н,е,ж},{м,о,н,е,т,а},{ж,е,м,а,н,с,т,в,о}

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

ОПРЕДЕЛЕНИЕ. Говорят, что множество А называется подмножеством множества

В, если каждый элемент множества A является элементом множества В.

Обозначение: А hello_html_21a8218f.gif В.

Следовательно, можно записать:

{н,о,ж}hello_html_21a8218f.gif{ м, н, о, ж , е, с, т, в, o}

{ж,е,т,о,н}hello_html_21a8218f.gif{ м, н, о, ж , е, с, т, в, o}

{с,о,н}hello_html_21a8218f.gif{н,о,с}

{н,о,с}hello_html_21a8218f.gif{с,о,н}

{ж,е,м,а,н,с,т,в,о}hello_html_21a8218f.gif{ м, н, о, ж , е, с, т, в, o}

{ м, н, о, ж , е, с, т, в, o}hello_html_21a8218f.gif{ж,е,м,а,н,с,т,в,о}

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

ОПРЕДЕЛЕНИЕ. Множества А и В называются равными, если они состоят из одних и тех же элементов. При этом пишут: А=B

Очевидно, что А = B тогда и только тогда, когда А hello_html_21a8218f.gif В и B hello_html_21a8218f.gifA. Таким образом для доказательства равенства множеств необходимо показать, что каждый элемент первого множества содержится во втором и каждый элемент второго - в первом. Таким образом мы можем записать, что {н,о,с}={с,о,н}и т.д.

Следует отметить, что пустое множество по определению считается подмножест­вом любого другого множества.

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

Во-первых, необходимо различать знаки hello_html_m7cb53dec.gif и hello_html_21a8218f.gif . В высказывании а hello_html_m7cb53dec.gifА знак hello_html_m7cb53dec.gif стоит между разнородными объектами: элемент и множество, в высказывании Аhello_html_21a8218f.gif B знак стоит между двумя множествами. Во-вторых, необходимо различать записи: {а} и а, для некоторого элемента а, и записи {A} и А для некоторого множества A. {а}hello_html_m88d8014.gifа, так как слева одноэлементное множества, а справа отдельный эле­мент. {A}hello_html_m88d8014.gif А так как слева множество А, состоящее из каких-то элементов, а справа одноэлементное множество, единственным элементом которого является - само множество А.


Примеры. 1) 1hello_html_m7cb53dec.gifN – истина; 1hello_html_m7cb53dec.gif{N} – ложь;

2) Пусть A={a,b}, тогда ahello_html_m7cb53dec.gifA – истина;{A}={a,b}- ложь; ahello_html_m7cb53dec.gif{A} – ложь;


Задания для самостоятельного решения:

11.Выясните какие из следующих высказываний истинны, а какие ложны.

  1. {1,2,3}={3,2,2,1}

  2. {1,{2,3}}={1,2,3}

  3. {{1,2}}={1,2}

  4. {1,2}hello_html_m7cb53dec.gif{{1,2,3},{1,3},1,2}

  5. {1,2}hello_html_21a8218f.gif{{1,2,3},{1,3},1,2}

  6. {1,2}hello_html_m7cb53dec.gif{{1,2},3,4}

  7. {1,2}hello_html_21a8218f.gif{{1,2},3,4}

  8. {1,2}hello_html_m7cb53dec.gif{1,2}

  9. 1hello_html_m7cb53dec.gif{1}

  10. 1hello_html_21a8218f.gif{1}

  11. Øhello_html_m7cb53dec.gif{ Ø,{ Ø }}

  12. Ø hello_html_m7cb53dec.gif{{ Ø }}

  13. Ø hello_html_21a8218f.gif{ Ø,{ Ø }}

  14. Ø ={ Ø }

  15. Ø hello_html_21a8218f.gif{{ Ø }}

  16. { Ø }hello_html_m7cb53dec.gif{{ Ø }}

12. Выпишите все подмножества множества {1,2,3}. Для каких четырех различных подмножеств A, B, C, D истинно (Ahello_html_21a8218f.gifB)hello_html_3af2f246.gif(C hello_html_21a8218f.gifD)hello_html_3af2f246.gif(Dhello_html_21a8218f.gifA)?

13. Для каждого из следующих наборов условий приведите примеры непустых различных множеств A,B,C,D,E, удовлетворяющих всем этим условиям.

  1. Dhello_html_21a8218f.gifC, Ehello_html_d009050.gifA, Bhello_html_d009050.gifD, Ahello_html_21a8218f.gifC.

  2. Ahello_html_d009050.gifC, Bhello_html_21a8218f.gifE, Dhello_html_21a8218f.gifA, Ehello_html_d009050.gifC.

  3. Dhello_html_21a8218f.gifA, Bhello_html_21a8218f.gifE, Ahello_html_d009050.gifE, Dhello_html_d009050.gifC, Bhello_html_21a8218f.gifE.

  4. Bhello_html_d009050.gifE, Ahello_html_21a8218f.gifD, Chello_html_21a8218f.gifD, Bhello_html_21a8218f.gifD, Ehello_html_21a8218f.gifA.

  5. Ahello_html_21a8218f.gifB, Dhello_html_d009050.gifC, Bhello_html_21a8218f.gifC, Ehello_html_d009050.gifD, Ahello_html_21a8218f.gifE.

  6. Bhello_html_d009050.gifE, Ahello_html_21a8218f.gifD, Chello_html_d009050.gifD, Bhello_html_21a8218f.gifD, Ehello_html_21a8218f.gifA.





Операции над множествами.


ОПРЕДЕЛЕНИЕ. Объединением двух множеств А и В называется множество, обозна­чаемое Ahello_html_m2c0134f2.gifВ и состоящее из тех и только тех элементов, которые принадлежат , хотя бы одному из множеств А или В.

Таким образом: х hello_html_m7cb53dec.gifAhello_html_m2c0134f2.gifB hello_html_m739d14ab.gif хhello_html_m7cb53dec.gifАhello_html_709f5f78.gifхhello_html_m7cb53dec.gifВ

ОПРЕДЕЛЕНИЕ. Пересечением двух множеств А и В называется множество, обозна­чаемое Ahello_html_m3f510064.gifB и состоящее из всех тех и только тех элементов, которые принад­лежат и множеству А и множеству B.

Таким образом: х hello_html_m7cb53dec.gifAhello_html_m3f510064.gifB hello_html_m739d14ab.gif хhello_html_m7cb53dec.gifАhello_html_3af2f246.gifхhello_html_m7cb53dec.gifВ

ОПРЕДЕЛЕНИЕ. Разностью двух множеств А и В называется множество, обозна­чаемое A\В и состоящее из всех тех и только тех элементов, которые принад­лежат множеству А и не принадлежат множеству В.

Таким образом: х hello_html_m7cb53dec.gifA\B hello_html_m739d14ab.gif хhello_html_m7cb53dec.gifАhello_html_3af2f246.gifхhello_html_m69d35eb5.gifВ

Очень часто в математике рассматриваются множества, являющиеся подмножества­ми некоторого фиксированного множества, которое рассматривается как универ­сальное множество: множество R, множество треугольников, четырехугольнике!

ОПРЕДЕЛЕНИЕ. Пусть М - некоторое универсальное множество, Аhello_html_21a8218f.gifМ. Дополне­нием множества А до М называется множество, обозначаемое A` и состоящее из тех и только тех элементов М, которые не принадлежат А

Таким образом: xhello_html_m7cb53dec.gif A`hello_html_m739d14ab.gif xhello_html_m69d35eb5.gifA другими словами: А`=М\А. Рассмотрим еще одну операцию, которую можно выполнять как над двумя множес­твами, так и над любым конечным числом множеств.

ОПРЕДЕЛЕНИЕ. Пусть А и В множества. Декартовым произведением двух множеств А и В называется множество, обозначаемое Аhello_html_m7e6c7897.gifВ и состоящее из всех упорядоченных пар вида (а,в), где аhello_html_m7cb53dec.gifА и вhello_html_m7cb53dec.gifВ.

Таким образом: Аhello_html_m7e6c7897.gifВ={(a,b): аhello_html_m7cb53dec.gifАhello_html_3af2f246.gif вhello_html_m7cb53dec.gifВ}

Если А=В, то Аhello_html_m7e6c7897.gifA называют декартовым квадратом множества А и обозначают А2.

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

A1hello_html_m7e6c7897.gifA2hello_html_m7e6c7897.gifА3hello_html_m7e6c7897.gifhello_html_m7e6c7897.gifAn={( a1,a2,a3,…an): aihello_html_m7cb53dec.gifAi}

Пример:

Пусть A={1,2,3}, B={2,4,6}, тогда Ahello_html_m2c0134f2.gifB={1,2,3,4,6}, Ahello_html_m3f510064.gifB={2}, A\B={1,3}, B\A={4,6}.


Задания для самостоятельного решения.


14.Найдите множества Ahello_html_m2c0134f2.gifB, Ahello_html_m3f510064.gifB, A\B, B\A, если

  1. A={3,5,6,7,9}, B={4,6,7,8}

  2. A={3,5,6,7}, B={2,4,8}

  3. A={2,3,4,5,6}, B={3,4,5}

  4. A=Z, B=N

  5. A=R, B=Q

  6. A=Z, B=Q

  7. A=[0;2], B=[1;5]

  8. A=[0;2], B={0,4,6}

15.Перечислите элементы множеств X и Y, если

  1. X\Y={a,b} Y\X={c,d} Xhello_html_m3f510064.gifY={x,y,z}

  2. Xhello_html_m2c0134f2.gifY={a,b,c,d,e} Xhello_html_m3f510064.gifY={c,d} X\Y={a,e}

  3. Xhello_html_m2c0134f2.gifY={a,b,c,d} X hello_html_m3f510064.gifYX\Y={a}

  4. {X\Y}hello_html_m2c0134f2.gif{Y\X}={a,b,c,x,y,z} X hello_html_m3f510064.gifY={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)), при которых предикат превращается в истинное высказывание, называется множеством истинности предиката. Множество истинности предиката Р(х) обозначается следующим образом: {xhello_html_m7cb53dec.gifD(P(x)): P(x)}.

Читается эта запись так: “х из множества D(P(x)), такие что верно Р(х)”.

В дальнейшем будем обозначать множество истинности предиката P(x) как M(P(x)).

ОПРЕДЕЛЕНИЕ. Если множество истинности предиката совпадает с его областью определения, то предикат называется тождественно истинным. Если множество истинности предиката пусто, то предикат называется тождественно ложным.

Примерами предикатов являются уравнения и неравенства с одной переменной. Выражением “xhello_html_m7cb53dec.gifD обладает свойством Р” также является предикатом, то есть предикат можно рассматривать как свойство того или иного объекта, при этом множество истинности - это множество объектов, обладающих свойством P.


Равносильность предикатов.


Пусть даны два предиката P(x) и Q(x) и D(P(x))hello_html_m3f510064.gifD(Q(x))=D.

ОПРЕДЕЛЕНИЕ. Предикат Q(x) называется логическим следствием предиката Р(x), если предикат Q(x) обращается в истинное высказывание при всех тех значениях переменной из множества Д, при которых истинен предикат Р(x), то есть если M(P(x))hello_html_21a8218f.gifM(Q(x)).

Обозначают это так: Р(х)hello_html_m4855e294.gifQ(х)

Из определения следует, что если Р(х)hello_html_m4855e294.gifQ(х), то для любого конкретного х0 верно высказывание P0)hello_html_m6bb904b4.gifQ(х0).

ОПРЕДЕЛЕНИЕ. Предикаты Р(х) и Q(х) называются равносильными, если предикат Р(х) обращается в истинное высказывания при тех и только тех значениях переменных из множества D, при которых истинен Q(х), то есть если M(P(x))= M(Q(x)).

Обозначают это так : Р(x)hello_html_m739d14ab.gifQ(x).

Из рассмотренных определений следует, что два предиката равносильны тогда и только тогда, когда каждый из них является логическим следствием другого. В частности, из определений следует, что любой предикат является логическим следствием любого тождественно-ложного предиката, Ø hello_html_21a8218f.gif M(P(x)) при любом Р(х)). Все тождественно-истинные предикаты, заданные на одном и том же множестве, равносильны между собой. Все тожественно- ложные предикаты, заданные на одном и том же множестве равносильны между собой.


Задания для самостоятельного решения.

15. Перечислить элементы каждого из следующих множеств.

  1. {x hello_html_m7cb53dec.gifN : x2-x-6=0}

  2. {x hello_html_m7cb53dec.gifZ: x2-4hello_html_3813d461.gif0}

  3. {x hello_html_m7cb53dec.gifR:lg(x+1)=hello_html_2d465846.gif}

  4. {n hello_html_m7cb53dec.gifN: hello_html_74f4579b.gif}

  5. {q hello_html_m7cb53dec.gifN: 24hello_html_3321970c.gifq hello_html_3af2f246.gifqhello_html_3321970c.gif2}

16.При каких ahello_html_m7cb53dec.gifR выполнено:

  1. hello_html_m7fb8c6fd.gifhello_html_m7cb53dec.gif{-1,1,2}

  2. -1hello_html_m7cb53dec.gif{hello_html_4b4b875b.gif, 2a-1, hello_html_m7fb8c6fd.gif}

  3. {1,a,a2-1,3}={1,3}

  4. a+1 hello_html_m7cb53dec.gif {1,-1, hello_html_m5a66fc59.gif}

  5. {1,-1,2}hello_html_21a8218f.gif {2-a,-1,2,3,hello_html_m9624a6.gif}

  6. {a,a2,a3}hello_html_21a8218f.gif[0;27]

  7. {1,-1,3}hello_html_21a8218f.gif{-a,-3,2a-1,2}

  8. {hello_html_m7fb8c6fd.gif,hello_html_m5a66fc59.gif}={a-1,a+1}

17. При каких a количество элементов множества {a,a2,a3}

  1. равно 2

  2. равно 1

18. Пусть Bt=[t-1;t+1], thello_html_m7cb53dec.gifR

  1. при каких t Bthello_html_m88d8014.gifhello_html_m53d4ecad.gif Ø

  2. при каких t 10hello_html_m7cb53dec.gifBt hello_html_3af2f246.gif 10.5hello_html_m69d35eb5.gif Bt

  3. при каких xhello_html_m7cb53dec.gifR xhello_html_m7cb53dec.gifB10 hello_html_3af2f246.gifxhello_html_m69d35eb5.gif B10.5

  4. при каких x hello_html_m7cb53dec.gifR xhello_html_m7cb53dec.gifB10 hello_html_3af2f246.gifx+0.1hello_html_m69d35eb5.gif B10

  5. при каких x hello_html_m7cb53dec.gifR xhello_html_m69d35eb5.gifB10 hello_html_3af2f246.gifx+0.1hello_html_m7cb53dec.gifB10


Одноместные и многоместные предикаты.


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

ОПРЕДЕЛЕНИЕ. Пусть даны множества A1, A2, Aз,..., Аn. Предикатом Р(x1,…xn) с областью определения A1hello_html_m7e6c7897.gifA2hello_html_m7e6c7897.gifAзhello_html_m7e6c7897.gif...hello_html_m7e6c7897.gifАn называется выражение, содержащее n переменных x1,x2xn, превращающееся в высказывание (истинное или ложное) при подстановке вместо переменных элементов из множеств A1, A2, Aз,..., Аn соот­ветственно.

Примеры.

Р(х,у): x-y = 5

Область определения: R2. Множество истинности:M={(x,y)hello_html_m7cb53dec.gifR2: y=x-5}

Р(х,у,z): x2+y2 = z2

Область определения: R3.

Множество истинности:M={(x,y,z)hello_html_m7cb53dec.gifR3: x2+y2=z2}


Операции над предикатами.


При конкретных значениях переменных предикаты как и высказывания принимают

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

операции.

Пусть Р(х) и Q (х) два одноместных предиката от одной и той же перемен­ной такие, что

DP(x)hello_html_21a8218f.gifD; DQ(x)hello_html_21a8218f.gifD.

ОПРЕДЕЛЕНИЕ. Отрицанием предиката Р(х) называется новый предикат, обозна­чаемыйhello_html_m382c1dc9.gifP(x), определенный на том же множестве, который принимает значение истины при тех значениях переменной, при которых Р(х) принимает значение ложь и наоборот. Таким образом, Mhello_html_m382c1dc9.gifP(x)=DP(x)\MP(x)

ОПРЕДЕЛЕНИЕ. Конъюнкцией предикатов Р(х) и Q(х) называется новый предикат, обозначаемый Р(х)hello_html_3af2f246.gifQ(х), заданный на DP(x)hello_html_m3f510064.gifDQ(x) , который обращается в истинное высказывание для тех и только тех значений переменной, для которых ис­тины оба предиката Р(х) и Q(х). Таким образом, MP(x)hello_html_3af2f246.gifQ(x)=MP(x)hello_html_m3f510064.gifMQ(x)

Пример: hello_html_21b6b017.gif - конъюнкция предикатов

ОПРЕДЕЛЕНИЕ. Дизъюнкцией двух предикатов Р(х) и Q(х) называется новый пре­дикат, обозначаемый P(x)hello_html_709f5f78.gifQ(x), заданный на DP(x)hello_html_m3f510064.gifDQ(x), который превращается в истинное высказывание для тех и только тех значений переменных, для которых истинен хотя бы один из предикатов Р(х) или Q(х).Таким образом MP(x)hello_html_709f5f78.gifQ(x)=MP(x)hello_html_m2c0134f2.gifMQ(x)

Пример:hello_html_5d62a7b5.gif - дизъюнкция предикатов

ОПРЕДЕЛЕНИЕ. Импликацией предикатов Р(х) и Q(х) называется новый предикат, который обозначается P(x)hello_html_m6bb904b4.gifQ(x), заданный на DP(x)hello_html_m3f510064.gifDQ(x), который превращается в ложное высказывание для тех и только тех значений переменной для которых P(x)- истинен, а Q(х) – ложен. Таким образом MP(x)hello_html_m6bb904b4.gifQ(x)=Mhello_html_m382c1dc9.gifP(x)hello_html_m2c0134f2.gifMQ(x)

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

Пример: hello_html_58a23114.gif - конъюнкция двух двухместных предикатов


КВАНТОРЫ.


Рассмотрим для начала одноместный предикат: Р(х): х - четное число.

D(P(x)) - множество целых чисел. Прочитаем следующие выражения:

  1. Р(8) :"8 - четное число"

  2. Р(7) :" 7 - четное число"

  3. Для всех х Р(х):"Любое целое число x - четное"

  4. Для некоторых х P(x): "Некоторые целые числа х - четные"

Предложение 1 - истинное высказывание, предложение 2 - ложное высказывание. Эти высказывания получены заменой в предикате переменной х конкретными числами. Предложения 3 и 4 - тоже высказывания, 3 - ложное, 4 - истинное. Но получены эти высказывания из предиката не заменой переменной конкретным числом, а употреблением выражений "для всех х" и "для некоторых х".

ОПРЕДЕЛЕНИЕ. Операция превращения предиката в высказывание с помощью приписывания квантора называется квантификацией (или "навешиванием кванторов"). Рассматриваются два квантора: квантор всеобщности и квантор существования. Квантор всеобщности обозначается перевернутой буквой А: hello_html_2bdadc34.gif (от англий­ского слова All - все. Квантор существования обозначается перевернутой буквой Е: hello_html_m3b861daf.gif от (от английского слова Exist – существовать).

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

hello_html_2bdadc34.gifхhello_html_m7cb53dec.gifD: Р(х) - читают "Для любого х из D: Р(х)

hello_html_m3b861daf.gifхhello_html_m7cb53dec.gifD: Р(х) - читают "Существует х из D, такое, что Р(х)"

Если понятно, из какого множества берут элемент х, то пишут просто: hello_html_2bdadc34.gifх: Р(х) hello_html_m3b861daf.gif х: Р(х)

Еcли мы имеем n -местный предикат, то кванторы можно" навесить" либо на все переменные, либо на часть из них. Переменная, на которую "навешан" квантор, называется связанной, а остальные переменные называются свободными. Если все переменные связаны, то предикат перестает быть предикатом и становится высказыванием (истинным или ложным). Если некоторые переменные связаны, а часть переменных осталась свободной, то получаем предикат о меньшим числом переменных. Например: hello_html_2bdadc34.gifxhello_html_m7cb53dec.gifRhello_html_m3b861daf.gifxhello_html_m7cb53dec.gifR - истинное высказывание;

hello_html_2bdadc34.gifxhello_html_m7cb53dec.gifZ x + y hello_html_3321970c.gif 5 - одноместный предикат от y;

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

ОПРЕДЕЛЕНИЕ. Высказывание hello_html_2bdadc34.gifхhello_html_m7cb53dec.gifD: Р(х) является истинным тогда и только, когда множество истинности предиката Р(х) совпадает с его областью определения то есть, если Р(х) - тождественно истинный предикат.

Пример : hello_html_2bdadc34.gifxhello_html_m7cb53dec.gifR x2+1>0 - истинное высказывание.

Из определения следует, что высказывание hello_html_2bdadc34.gifх: Р(х) ложно тогда и только

тогда, когда при некотором х0hello_html_m7cb53dec.gifD высказывание P(x0) - ложно.

ОПРЕДЕЛЕНИЕ. Элемент х0hello_html_m7cb53dec.gifD, для которого P(x0) – ложно, называется контр-

примером для высказыванияhello_html_2bdadc34.gifх: Р(х).

Примеры: hello_html_2bdadc34.gifxhello_html_m7cb53dec.gifR x2+3x-2>0 – ложь, так как при x0x02+3x0-2 < 0; x0 =0 – контрпример;

ОПРЕДЕЛЕНИЕ. Высказывание hello_html_m3b861daf.gif хhello_html_m7cb53dec.gifD: Р(х) является истинным тогда и только

тогда, когда множество истинности предиката Р(х) не пусто: M(P(X))hello_html_m88d8014.gif Ø, то

есть Р(х) не является тождественно ложным предикатом.

Из определения следует, что для того, чтобы доказать, что высказывание с

квантором существования истинно достаточно предъявить элемент из множества

D, при котором Р(х) будет истинно.

Примеры: hello_html_m3b861daf.gif хhello_html_m7cb53dec.gifR: x2-1=0 - истина, так как 1hello_html_m7cb53dec.gifM(P(X)), то есть M(P(X))hello_html_m88d8014.gif Ø

hello_html_m3b861daf.gifхhello_html_m7cb53dec.gifR: x2-x+100=0 - ложь, так как M(P(X))hello_html_m88d8014.gif Ø

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

Пусть Р(х,у) - эти предикат: "официант х обслуживает стол уи. Тогда прочи­таем следующие высказывания:

hello_html_2bdadc34.gifxhello_html_m3b861daf.gify P(x,y) - каждый официант имеет стол, который он обслуживает;

hello_html_2bdadc34.gifyhello_html_m3b861daf.gify Р(х,у) - для каждого стола есть официант, который его обслуживает;

hello_html_m3b861daf.gifyhello_html_2bdadc34.gifx Р(х,у) - существует стол, который обслуживается любым официантом;

hello_html_m3b861daf.gifxhello_html_2bdadc34.gify Р(х,у) - существует официант, который обслуживает любой стол.


Задания для самостоятельного решения.

19. Определить истины или ложны высказывания на множестве R.

hello_html_2bdadc34.gifxhello_html_2bdadc34.gify x+y=7

hello_html_m3b861daf.gifyhello_html_2bdadc34.gifx x+y=7

hello_html_m3b861daf.gifx hello_html_m3b861daf.gify x+y=7

hello_html_2bdadc34.gifyhello_html_m3b861daf.gify x+y=7

hello_html_2bdadc34.gifxhello_html_m3b861daf.gify y>x

hello_html_m3b861daf.gifyhello_html_2bdadc34.gifx y>x

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


20.Записать следующие фразы на языке предикатов и кванторов.

Bce рыбы плавают.

Ни одна собака не умеет мяукать

Кто хочет, тот добьется

Если кто-нибудь может прыгнуть в окно, то и Вася может

Либо каждый любит кого-нибудь и ни один не любит всех, либо некто любит всех и кто-то не любит никого.


Отрицание высказываний с кванторами.

Для того, что бы способ построения высказываний, содержащий отрицание и кванторы

стал более наглядным, рассмотрим примеры.

Произнести следующие предложения, не употребляя слова "неправда”:

1. Неправда, что все рыбы плавают.

2. Неправда, что некоторые реки впадают в Каспийское море.

Совершенно очевидно, что в русском языке вместо предложения 1 мы скажем: "есть рыбы, которые не умеют плавать", а вместо предложения 2 - "каждая река не впадает в Каспийское море". Эти примеры показывают, что справедливы следующие формулы:

hello_html_m382c1dc9.gif(hello_html_2bdadc34.gifx Р(х)) hello_html_65afd3a0.gif hello_html_m3b861daf.gifx (hello_html_m382c1dc9.gifP(x)) (1)

hello_html_m382c1dc9.gif(hello_html_m3b861daf.gifx Р(х)) hello_html_65afd3a0.gifhello_html_2bdadc34.gifx (hello_html_m382c1dc9.gifP(x)) (2)

Доказательство:

  1. hello_html_m382c1dc9.gif(hello_html_2bdadc34.gifx Р(х)) = Л hello_html_65afd3a0.gifhello_html_2bdadc34.gifx Р(х) = И hello_html_65afd3a0.gifM(P(x))=D hello_html_65afd3a0.gifM(hello_html_m382c1dc9.gifP(x))=Ø hello_html_65afd3a0.gifhello_html_m3b861daf.gifx (hello_html_m382c1dc9.gifP(x))=Л

  2. hello_html_m382c1dc9.gif(hello_html_m3b861daf.gifx Р(х)) = И hello_html_65afd3a0.gifhello_html_m3b861daf.gifx Р(х) = Л hello_html_65afd3a0.gifM(P(x))= Ø hello_html_65afd3a0.gifM(hello_html_m382c1dc9.gifP(x))=D\ Ø hello_html_65afd3a0.gifhello_html_2bdadc34.gifx (hello_html_m382c1dc9.gifP(x))=И


Задания для самостоятельного решения.:

21.hello_html_m382c1dc9.gif(hello_html_2bdadc34.gifxhello_html_m3b861daf.gify P(x,y)) hello_html_65afd3a0.gif hello_html_m3b861daf.gifxhello_html_m382c1dc9.gif(hello_html_m3b861daf.gify P(x,y)) hello_html_65afd3a0.gif hello_html_m3b861daf.gifxhello_html_2bdadc34.gifyhello_html_m382c1dc9.gifP(x)

22.Произнести предложение, не употребляя слово "неправда":

"Неправда, что некотором поезде, идущем из Санкт-Петербурга в Москву, в каждом вагоне есть свободное место".

В каждом поезде, идущем из Санкт-Петербурга в Москву существует вагон, в котором все места заняты".

23.Пусть П(х) - x - простое число;

Ч(х) - х - четное число;

Н(х) - х -нечетное числе;

Д(х,у) - y делится на х ;

Прочитать и построить отрицание к формуле:

(hello_html_2bdadc34.gifx (Ч(x)hello_html_m6bb904b4.gif (hello_html_2bdadc34.gify Д(x,y) hello_html_m6bb904b4.gifЧ(y))























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


Выберите специальность, которую Вы хотите получить:

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

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Автор
Дата добавления 03.05.2016
Раздел Информатика
Подраздел Другие методич. материалы
Просмотров158
Номер материала ДБ-063724
Получить свидетельство о публикации
Похожие материалы

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