РАВНОСИЛЬНОСТЬ ФОРМУЛ АЛГЕБРЫ ВЫСКАЗЫВАНИЙ

МАТЕМАТИЧЕСКАЯ ЛОГИКА

АЛГЕБРА ВЫСКАЗЫВАНИЙ

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

Классификация предложений естественного языка. Суждение, истинностное значение суждения: истина (1) или ложь (0). Классификация суждений по возможности определения их истинностных значений: определенные и неопределенные суждения. Виды неопределенности суждений (неопределенность частного суждения, возникшая из-за возможности расширения объема субъекта, из-за недостаточной информации о связи между терминами суждения, из-за многозначности терминов суждения, из-за использования переменной в качестве субъекта или предиката). Высказывание. Классификация высказываний по структуре: простые и сложные. Логические операции, их символьное обозначение и содержательный смысл. Алгебра высказываний, то есть множество всех высказываний с определенными на нем логическими операциями: , где  – множество всех высказываний.

 

 

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

 

 

 

 

8.1.Среди следующих предложений указать определенные и неопределенные суждения. В неопределенных суждениях установить вид неопределенности. Для определенных суждений (высказываний) определить истинностное значение.

1) Море штормит.

2) Иногда море штормит.

3) Море всегда штормит.

4) Любое море штормит.

5) Любое море иногда штормит.

6) Всегда какое-либо море штормит.

7) В море шторм?

8) Копейка рубль бережет.

9) Не переходи улицу на красный свет светофора!

10) Ученик решил задачу.

11) Ученик знает теорему Пифагора.

12) Любой ученик знает теорему Пифагора.

13) Какой русский не любит быстрой езды?

14) Множество  счетно.

15) Поле не имеет делителей нуля.

16) Данный многочлен не имеет вещественных корней.

 

8.2.Определить истинностные значения простых высказываний, используя диаграммы Эйлера-Венна для демонстрации отношений между их терминами:

1) Все люди подвержены заболеваниям.

2) Некоторые философы – математики.

3) Все алгебраические кольца являются полями.

4) Среди цветов встречаются хищники.

5) Галактики разлетаются со скоростью, которая может приближаться к скорости света.

6) Ни один политик не исповедует буддизм.

7) Некоторые растения не переносят обильного полива.

8) Последний император Германии Вильгельм II проводил милитаристическую политику.

9) Все европейские государства участвовали во Второй Мировой Войне.

10) Некоторые прямые не пересекаются и не параллельны.

11) Не существует живородящих рыб.

12) Агата Кристи – мастер детективного жанра.

13) Уравнение  имеет решение в поле рациональных чисел.

 

8.3.Вычислить истинностные значения сложных высказываний по значениям составляющих его простых высказываний:

1) , если , , ;

2) , если , , ;

3) , если , , ;

4)  на наборах , , .

 

8.4. Известно, что  и . Определить истинностное значение .

 

8.5.Известно, что . Определить истинностные значения высказываний:

, , , .

8.6. Записать символьные модели высказываний и определить их истинностные значения:

1) Либо  делится на , либо  делится на .

2) Сумма углов четырехугольника меньше или равна .

3) , .

4) Так как город Нижний Новгород был в советское время переименован в «город Горький», а город Царицын – в «город Сталинград», то .

5) Тигр – травоядное животное, следовательно, Джон Кеннеди – президент Франции.

6) Луна не спутница Земли, если .

7) Равенство  достаточно для равенства .

8) Для равенства  необходимо, чтобы  или .

9) Для равенства  достаточно, чтобы , а .

10) Неверно, что если , то .

11) Нидерланды относятся к экономически слаборазвитым странам, если и только если Россия – крупнейший экспортер нефти.

12) Вертикальные или внутренние накрест лежащие углы при параллельных прямых и секущей равны.

 

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

1) ;

2) ;

3) .

 

8.8.Беседуют трое друзей: Белокуров, Рыжов и Чернов. Брюнет сказал Белокурову: «Любопытно, что один из нас блондин, другой – брюнет, третий – рыжий, но ни у кого цвет волос не соответствует фамилии». Какой цвет волос у каждого из друзей?

 

8.9.В бутылке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что:

а) вода и молоко не в бутылке;

б) сосуд с лимонадом стоит между кувшином и квасом;

в) в банке не лимонад и не вода;

г) стакан стоит между банкой и сосудом с молоком.

В каком сосуде находится каждая из жидкостей?

 

8.10. В очереди за билетами в кино стоят друзья: Юра, Миша, Володя, Саша и Олег. Известно, что Юра купит билет раньше, чем Миша, но позже Олега, Володя и Олег не стоят рядом, а Саша не находится рядом ни с Олегом, ни с Юрой, ни с Володей. Кто за кем стоит?

 

8.11. Смит, Джонсон и Робинсон работают в одном поезде машинистом, кондуктором и кочегаром. В поезде едут три пассажира с теми же фамилиями. (Пассажира будем называть «Мистер» (М-р).) М-р Робинсон живет в Лос-Анджелесе, кондуктор – в Омахе. М-р Джонсон давно позабыл всю алгебру, которой его учили в колледже. Однофамилец кондуктора живет в Чикаго. Кондуктор и один из пассажиров, известный специалист по математической логике, ходят в одну церковь. Смит всегда выигрывает у кочегара партию в бильярд. Как фамилия машиниста?

 

ФОРМУЛЫ АЛГЕБРЫ ВЫСКАЗЫВАНИЙ

 

Высказывательная переменная и ее истинностное значение. Число всевозможных распределений истинностных значений  высказывательных переменных. Формула алгебры высказываний. Подформула. Соглашение о порядке выполнения в формуле логических операций. Таблицы истинности. Типы формул: выполнимая формула, опровержимая формула, тождественно истинная формула (тавтология) и тождественно ложная формула (противоречие).

 

9.1.   Указать выражения, являющиеся формулами алгебры высказываний:

1) ;

2) ;

3) ;

4) ;

5) ;

6) ;

7) .

 

9.2.   Исключить возможно большее число скобок в формулах:

1) ;

2) ;

3) .

 

9.3.   Восстановить скобки в формулах:

1) ;

2) ;

3) .

 

9.4.   Выписать все подформулы следующих формул, учитывая соглашение о порядке выполнения логических операций:

1) ;

2) ;

3) ;

4) ;

5) ;

6) .

 

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

 

9.6. Построить таблицы истинности для следующих формул. Определить тип формул:

1) ;

2) ;

3) ;

4) ;

5) ;

6) ;

7) ;

8) ;

9) .

 

9.7.   Ключ от замка спрятан в одной из трех шкатулок (черной, белой, красной), на крышках которых сделаны надписи:

на черной: ключ не в белой шкатулке;

на белой: ключ не в этой шкатулке;

на красной: ключ в этой шкатулке.

В какой шкатулке ключ, если известно, что из трех надписей на крышках, по крайней мере, одна истинна и, по крайней мере, одна ложна?

 

9.8.   В доме живут А, его жена Б и трое их детей В, Г, Д, при этом справедливы следующие утверждения:

а) Если А смотрит телевизор, то и Б смотрит телевизор.

б) Хотя бы один из Г и Д смотрит телевизор.

в) Ровно один из Б и В смотрит телевизор.

г) В и Г либо оба смотрят, либо оба не смотрят телевизор.

д) Если Д смотрит телевизор, то А и Г тоже смотрят телевизор.

Кто смотрит и кто не смотрит телевизор?

 

9.9.   Андрей и Борис разговаривали о предстоящей контрольной работе по математической логике. Андрей сказал: «Если я справлюсь с работой, то ты с ней тоже справишься». Борис ответил: «А если я не справлюсь с работой, то и ты с ней не справишься». Докажите, что во время этого разговора или оба говорят правду, или оба лгут.

 

9.10.   Пять девушек: Анна, Белла, Вера, Галина и Дарья – вышли в финал конкурса красоты. На вопрос Дарье: «Кто старше: Вы или Белла?», журналист получил следующий ответ: «Если я старше Анны, то я старше Беллы, либо моложе Веры. Если же я не старше Беллы, то я моложе Галины. Если я моложе Галины и старше Анны, то я не моложе Веры. Если я моложе Галины и не старше Беллы, то я старше Анны». Каков правильный ответ не вопрос журналиста?

 

9.11.   Для полярной экспедиции из восьми претендентов: A, B, C, D, E, F, G и H надо отобрать шесть специалистов: биолога, гидролога, синоптика, радиста, механика и врача. Обязанность биолога могут выполнять E и G, гидролога – B и F, синоптика – G и F, радиста – C и D, механика – C и H, врача – A и D. Хотя некоторые претенденты владеют двумя специальностями, в экспедиции каждый сможет выполнять только одну обязанность. Кого и кем следует взять в экспедицию, если F не сможет ехать без B, D – без H и без C, C не может ехать одновременно с G, а A вместе с B?

 

9.12.   В гимназии, перешедшей на самообслуживание, четырем старшеклассникам: Андрееву, Костину, Савельеву и Давыдову поручили убрать седьмой, восьмой, девятый и десятый классы. При проверке оказалось, что десятый класс плохо убран. Не ушедшие домой ученики сообщили следующее. Андреев: «Я убирал девятый класс, а Савельев – седьмой»;

Костин: «Я убирал девятый класс, а Андреев – восьмой класс»;

Савельев: «Я убирал восьмой класс, а Костин – десятый класс».

Давыдов ушел домой. Оказалось, что каждый ученик одну половину говорил правильно, а другую – неправильно. Какой класс убирал каждый ученик?

 

РАВНОСИЛЬНОСТЬ ФОРМУЛ АЛГЕБРЫ ВЫСКАЗЫВАНИЙ

 

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

Правила равносильных преобразований формул алгебры высказываний (правилo подстановки). Методы доказательства равносильности формул: посредством равносильных преобразований и с помощью таблицы истинности. Совместность множества формул. Упрощение систем высказываний.

 

10.1. Доказать, что на множестве формул алгебры высказываний отношение равносильности формул является отношением эквивалентности.

 

10.2. Доказать законы алгебры высказываний:

1)                                                                закон тождества;

2)                                                      закон двойного отрицания;

3)  и                                   законы идемпотентности;

4) ,  и , ;

5)                                     закон исключенного третьего;

6)                                               закон противоречия;

7)  и                        законы коммутативности;

8)  и        законы ассоциативности;

9)                                                          законы

и                                  дистрибутивности;

10)                                  закон замены импликации;

11)               закон удаления эквиваленции;

12)  и                      законы де Моргана;

13)  и                                законы поглощения;

14)  и               законы склеивания;

15)                                 закон контрапозиции;

16)                        закон силлогизма;

17)                                    закон заключения.

 

10.3. Докажите равносильность следующих формул двумя способами: посредством равносильных преобразований и с помощью таблиц истинности:

1)  и ;

2)  и ;

3)  и ;

4)  и ;

5)  и ;

6)  и ;

7)  и ;

8)  и ;

9)  и .

 

10.4.   Доказать, что существует  неэквивалентных формул от  переменных.

 

10.5.   Пусть формулы  и  эквивалентны и  является подформулой формулы . Доказать, что если формула  получена из формулы  подстановкой вместо подформулы  формулы , то  и эквивалентны.

 

10.6.   Упростить следующие формулы посредством равносильных преобразований:

1) ;

2) ;

3) ;

4) ;

5) ;

6) ;

7) ;

8) ;

9) .

 

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

1) ;

2) ;

3) ;

4) ;

5) .

 

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

 

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

 

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

 

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

 

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

 

10.13.   Пусть буквы , ,  обозначают суждения:

 – «Множество рациональных чисел счетно»,

 – «Множество рациональных чисел конечно»,

 – «Множество комплексных чисел счетно».

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

 

10.14.   Формализовать утверждения и привести их по возможности к более простому виду:

1) Если функция непрерывна в данной точке, то она не имеет в ней разрыва; функция имеет разрыв в данной точке.

2) Либо Санчо Панса станет губернатором, либо Дон Кихот – не доблестный рыцарь, а Дон Кихот – доблестный рыцарь, так как Дульцинея Тобосская любит только доблестных рыцарей.

3) Если треугольник равносторонний, то все углы в треугольнике равны или все его высоты имеют одинаковую длину; и неверно, что треугольник равносторонний, но высоты треугольника не равны.

4) Необходимым условием победы спортсмена является его хорошая физическая форма.

5) Хорошей физической формы спортсмена не достаточно для его победы.

6) Чтобы быть допущенным к экзамену необходимо и достаточно сдать зачет.

7) Чтобы сдать экзамен, необходимо, но не достаточно сдать зачет.

8) Чтобы улучшить состояние здоровья достаточно, но не необходимо съездить на море.

9) Отрезки , ,  являются сторонами треугольника, если , но для того чтобы отрезки , ,  не являлись сторонами треугольника, необходимо, чтобы .

10) Чтобы Боб был счастлив, достаточно, чтобы ему купили велосипед или отпустили в кино; чтобы Боб был счастлив и его отпустили в кино, необходимо, чтобы ему купили велосипед; Боб счастлив, так как ему купят велосипед и отпустят в кино.

 

 

10.15.   До царя Гороха дошла молва, что кто-то из троих богатырей убил Змея Горыныча. Царь приказал всем троим явиться ко двору и молвили они:

Илья Муромец:   «Змея убил Добрыня Никитич»;

Добрыня Никитич:  «Змея убил Алеша Попович»;

Алеша Попович:   «Я убил Змея».

При этом известно, что один из них сказал правду, а двое слукавили. Кто убил змея?

 

 

10.16.   В велогонках приняли участие пять школьников. После гонок пять болельщиков заявили:

«Коля занял первое место, а Ваня – четвертое»;

«Сережа занял второе место, а Ваня – четвертое»;

«Сережа занял второе место, а Коля – третье»;

«Толя занял первое место, а Надя – второе»;

«Надя заняла третье место, а Толя – пятое».

Зная, что одно из показаний каждого болельщика верное, а другое - неверное, найти правильное распределение мест.

 

 

10.17.   В стране Чудес проводилось следствие по делу об украденной муке. На суде Мартовский Заяц заявил, что муку украл Болванщик. В свою очередь Болванщик и Соня дали показания, которые по каким-то причинам не были записаны. В ходе судебного заседания выяснилось, что муку украл лишь один из трех подсудимых и что только он дал правдивые показания. Кто украл муку?

---

Дата добавления: 2018-04-05; просмотров: 761; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!