ВЕЛИКИЙ НОВГОРОД

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

НОВГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИМЕНИ ЯРОСЛАВА МУДРОГО

 

 

АЛГЕБРА ЛОГИКИ

Учебно-методическое пособие

 

 

ВЕЛИКИЙ НОВГОРОД

УДК 510.633. Печатается по решению ББК 22.1 РИС НовГУ  

ВВЕДЕНИЕ

В пособии приводятся необходимые теоретические сведения и образцы решения задач по основным темам раздела «Алгебра логики»:

– высказывания и логические операции над ними;

– равносильные формулы алгебры логики;

– функции алгебры логики;

– совершенные нормальные формы;

– некоторые приложения.

Теоретический материал почерпнут, в основном, из указанного выше учебного пособия Л.М. Лихтарникова [9]. По указанным темам приведены примеры решения типовых задач и задачи для самостоятельной работы. В конце пособия содержатся контрольные вопросы и контрольные задания.

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

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

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

Понятие высказывания

и запутанного мышления; она рассеивает туман. Д.-С.Милль

Логические операции над высказываниями

Из высказываний с помощью логических связок образуются новые высказывания. Рассмотрим основные логические связки (табл. 1).

 

Таблица 1

Основные логические связки

Определение 1. Отрицанием высказывания x называется новое высказывание,… Определение 2.Конъюнкцией (логическим умножением) двух высказываний x и y, называется новое высказывание, которое…

Формулы алгебры логики

С помощью логических операций над высказываниями можно строить различные сложные высказывания. Порядок выполнения операций указывается скобками.… Сложные высказывания, которые могут быть получены из элементарных высказываний… Формулы алгебры логики будем обозначать большими буквами латинского алфавита: A, B, C, … .

Решение типовых задач

1) Какая прекрасная погода! 2) Великий Новгород стоит на Волхове. Решение.

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

1) Москва – столица России; 2) cтудент механико-математического факультета; 3) треугольник подобен треугольнику ;

РАВНОСИЛЬНЫЕ ФОРМУЛЫ АЛГЕБРЫ ЛОГИКИ. РАВНОСИЛЬНЫЕ ПРЕОБРАЗОВАНИЯ ФОРМУЛ

 

Три группы равносильностей

Определение 1. Две формулы алгебры логики А и В называются равносильными, если они принимают одинаковые логические значения на любом наборе значений… Запись АВ означает, что формулы А и В равносильны. Важнейшие равносильности можно разбить на три группы:

Равносильные преобразования формул

  Используя равносильности группы I, II и III, можно часть формул алгебры логики… Определение 1. Формула А называется тождественно истинной (или тавтологией), если она принимает значение «истина» при…

Примеры решения задач

 

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

Решение.

Запишем цепочку равносильных формул:

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

Решение.

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

Решение.

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

и .

Решение.

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

  Ι.Производя равносильные преобразования докажите, что формулы являются… 1) ;

ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ. СОВЕРШЕННЫЕ НОРМАЛЬНЫЕ ФОРМЫ. ПРОБЛЕМА РАЗРЕШИМОСТИ

Функии алгебры логики

Формула алгебры логики является функцией входящих в нее элементарных высказываний, ее аргументы принимают два значения: 0 и 1, при этом значение… Определение 1. Функцией алгебры логики от n переменных (или функцией Буля)… Функция задается своей истинностной таблицей (табл. 4).

Представление произвольной функции алгебры логики в виде формулы алгебры логики

Рассмотрим формулу (1) которая составлена следующим образом: каждое слагаемое этой логической суммы представляет собой конъюнкцию, в которой…

Совершенные нормальные формы алгебры логики

Определение 1. Элементарной конъюнкцией n переменных называется конъюнкция переменных или их отрицаний. Определение 2. Дизъюнктивной нормальной формой (ДНФ) формулы А называется… Определение 3. Совершенной дизъюнктивной нормальной формой (СДНФ) формулы А называется ДНФ А, обладающая свойствами…

Правило получения СДНФ формулы А с помощью равносильных преобразований.

2. Из ДНФ А путем равносильных преобразований получаем СДНФ, последовательно добиваясь выполнения четырех свойств СДНФ А: 1) Пусть В есть слагаемое ДНФ А, не содержащее . Тогда надо заменить… 2) Если в ДНФ А встретится два одинаковых слагаемых , то лишнее нужно отбросить, так как .

Правило получения СКНФ формулы А с помощью равносильных преобразований.

2. Из КНФ А путем равносильных преобразований получаем СКНФ А, последовательно добиваясь выполнения четырех свойств СКНФ А: 1) Если элементарная дизъюнкция В, входящая в КНФ А, не содержит переменную ,… 2) Если КНФ А содержит две одинаковых элементарных дизъюнкций, то одну можно отбросить, так как .

Проблема разрешимости

Все формулы алгебры логики делятся на три класса: 1) тождественно истинные, 2) тождественно ложные,

Примеры решения задач

 

Пример 1. По таблице истинности (табл. 8) найдите формулы, определяющие функции ии придайте им более простой вид (табл. 8):

Таблица 8

Решение. 1. Используя правило получения формулы алгебры логики из таблицы истинности для функции , получим

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

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

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

Пример 2. Используя СДНФ, найдите формулу, принимающую значение 1 на следующих наборах значений переменных, и только на них:

1. F(1,1,0)=F(0,1,0)=F(0,1,1)=1.

2. F(0,1,1,0)=F(1,0,1,1)=F(0,1,0,1)=1.

Решение. 1. Первому условию удовлетворяет лишь конъюнктивный одночлен , второму – , третьему – . Тогда формула F(x, y, z) обращается в 1, тогда и только тогда, когда обращается в 1, или обращается в 1, или обращается в 1. Следовательно, F(x, y, z) – искомая формула.

2. Первому условию удовлетворяет лишь конъюнктивный одночлен , второму – , третьему – . Тогда формула обращается в 1, тогда и только тогда, когда обращается в 1, или обращается в 1, или обращается в 1. Следовательно, F(x,y, z,s)–искомая формула.

Пример 3. Используя СКНФ, найдите формулу, принимающую значение 0 на следующих наборах значений переменных, и только на них:

1. F(0,1)=F(1,1)=0.

2. F(1,0,0)=F(1,0,1)=0.

Решение. 1. Первому условию удовлетворяет лишь дизъюнктивный одночлен , второму – . Тогда формула F(x, y) обращается в 0, тогда и только тогда, когда обращается в 0,или обращается в 0. Следовательно, F(x, y) – искомая формула.

2. Первому условию удовлетворяет лишь дизъюнктивный одночлен , второму – . Тогда формула F(x, y, z) обращается в 0, тогда и только тогда, когда обращается в 0, или обращается в 0. Следовательно, F(x, y, z) – искомая формула.

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

1. .

2. .

Решение.

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

Решение.

Пример 6.Применяя равносильные преобразования, найдите СДНФ для формул из задачи 4.

Решение.

Пример 7.Применяя равносильные преобразования, найдите СКНФ для формул из задачи 4.

Решение.

Пример 8.Для каждой из формул задачи4 с помощью её таблицы истинности найдите СДНФ и СКНФ.

Решение.

а) СДНФ А.

1. Составим таблицу истинности для формулы (табл. 9).

Таблица 9

 

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

б) СКНФ А.

Выбирая наборы значений переменных, на которых формула обращается в 0, запишем

а затем воспользуемся формулой двойственности

а) СДНФ В.

2. Составим таблицу истинности для формулы (табл. 10).

Таблица 10

 

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

б) СКНФ В.

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

Пример 9. Определить, к какому классу относится данная формула ?

Решение. Приведем формулу к какой-либо нормальной форме:

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

Это произведение не является тождественно истинным, так как элементарная сумма не тождественно истина. Таким образом, исходная формула не тождественно ложна и не тождественно истинна, следовательно, она выполнима.

 

Проверочная работа № 3

Функции алгебры логики. Совершенные нормальные формы алгебры логики. Проблема разрешимости

 

Ι.По таблицам истинности найдите формулы, определяющие функции и придайте им более простой вид (табл. 11, табл.12):

Таблица 11

 

Таблица 12

 

ΙΙ.Используя СДНФ, найдите формулу, принимающую значение 1 на следующих наборах значений переменных, и только на них:

1. F(0, 0)=F(1, 1)=1

2. F(0, 1)=F(1, 0)=1

3. F(1, 0)=F(1, 0)= F(1, 1)=1

4. F(1, 1)=F(0, 0)= F(1, 0)=1

5. F(1, 1, 0)=F(1, 0, 1)=1

6. F(0, 1, 1)=F(1, 1, 0)= 1

7. F(1, 0, 0)=F(0, 1, 0)= F(0, 0, 1)=1

8. F(0, 0, 0)=F(0, 1, 0)= F(1, 1, 1)=1

9. F(0, 1, 1)=F(1, 0, 1)= F(1, 1, 0)=1

10. F(1, 0, 1)=F(0, 1, 0)= F(0, 0, 0)=1

11. F(0, 1, 0)=F(1,0, 1)= F(1,1, 1)=1

12. F(1, 0, 0)=F(1, 1, 0)= F(0, 1, 0)=1

13. F(0, 1, 1)=F(1, 1, 1)= F(0, 1, 0)=1

14. F(1, 0, 0)=F(1, 1, 0)= F(0, 1, 0)=1

15. F(1, 1, 0, 0)=F(0, 0, 1, 1)=1

16. F(0,1,0,1)=F(1,0,1,0)= F(1,0,0,0)=F(1,1,1,0)=1

17. F(0,0,0,1)=F(1,1,1,0)= F(1,0,1,0)=F(1,1,0,0)=1

18. F(0,1,0,1)=F(1,0,1,0)= F(1,0,1,0)=F(1,1,1,0)=1

19. F(1,1,0,1)=F(1,0,1,0)= F(1,0,1,0)=F(1,0,0,1)=1

20. F(0,0,1,1)=F(0,1,1,0)= F(1,1,1,0)=F(0,1,0,1)=1

ΙΙΙ.Используя СКНФ, найдите формулу, принимающую значение 0 на следующих наборах значений переменных, и только на них:

1. F(0, 0)=F(1, 1)=0

2. F(0, 1)=F(1, 0)=0

3. F(1, 1)=F(0, 0)= F(1, 0)=0

4. F(1, 0)=F(1, 0)= F(1, 1)=0

5. F(1, 1, 0)=F(1, 0, 1)=0

6. F(0, 1, 1)=F(1, 1, 0)= 0

7. F(0, 1, 0)=F(1,0, 1)= F(1,1, 1)=0

8. F(1, 0, 0)=F(0, 1, 0)= F(0, 0, 1)=0

9. F(0, 1, 1)=F(1, 0, 1)= F(1, 1, 0)=0

10. F(1, 0, 1)=F(0, 1, 0)= F(0, 0, 0)=0

11. F(1, 0, 0)=F(1, 1, 0)= F(0, 1, 0)=0

12. F(0, 0, 0)=F(0, 1, 0)= F(1, 1, 1)=0

13. F(1, 0, 0)=F(1, 1, 0)= F(0, 1, 1)=0

14. F(0, 1, 1)=F(1, 1, 1)= F(0, 1, 0)=0

15. F(1, 1, 0, 0)=F(0, 0, 1, 1)=0

16. F(0,1,0,1)=F(1,0,1,0)= F(1,0,0,0)=F(1,1,1,0)=0

17. F(0,0,0,1)=F(1,1,1,0)= F(1,0,1,0)=F(1,1,0,0)=0

18. F(0,1,0,1)=F(1,0,1,0)= F(1,0,1,0)=F(1,1,1,0)=0

19. F(1,1,0,1)=F(1,0,1,0)= F(1,0,1,0)=F(1,0,0,1)=0

20. F(0,0,1,1)=F(0,1,1,0)= F(1,1,1,0)=F(0,1,0,1)=0

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

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

V. Приведите равносильными преобразованиямикаждую из формул задачи ΙV к конъюнктивной нормальной форме.

VΙ.Применяя равносильные преобразования, найдите СДНФ для

формул из задачи ΙV.

VΙΙ.Применяя равносильные преобразования, найдите СКНФ для

формул из задачи ΙV.

VΙΙΙ. Для каждой из формул задачиΙV с помощью её таблицы истинности

найдите СДНФ и СКНФ.

Некоторые приложения алгебры логики

Приложения алгебры логики в технике (релейно-контактные схемы)

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

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

Ещё в 1910 году физик П.С.Эренфест указал на возможность применения аппарата алгебры логики при исследовании релейно–контактных схем (РКС). Однако его идеи стали реализовываться значительно позже, когда создание общей теории конструирования РКС стало остро необходимым.

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

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

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

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

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

1) переключателей, которыми могут быть механические действующие устройства, электромагнитные реле, полупроводниковые элементы и т.д.;

2) соединяющих их проводников;

3) входов в схему и выходов из неё (клемм, на которые подаётся электрическое напряжение). Они называются полюсами схемы.

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

Схема 1.

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

Конъюнкция двух высказываний p и qбудет представлена двухполюсной схемой с последовательным соединением двух переключателей P и Q (схема 2).

 

 

Схема 2.

Эта схема пропускает ток тогда и только тогда, когда истинны и p, и q одновременно, то есть истинна конъюнкция p&q.

Дизъюнкция двух высказываний p и q изобразится двухполюсной схемой с параллельным соединением двух переключателей P и Q (схема 3).

Схема 3.

Эта схема пропускает ток в случае, если истинно высказывание р или истинно высказывание q, то есть истинна дизъюнкция p v q.

Если высказывание есть отрицание высказывания р, то тождественно истинная формула изображается схемой, которая проводит ток всегда( схема 4), а тождественно ложная формула изображается схемой, которая всегда разомкнута (схема 5).

Схема 4.

Схема 5.

Из схем 1, 2 и 3 путём последовательного и параллельного их соединения могут быть построены новые двухполюсные переключательные схемы, которые называют П–схемами.

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

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

Пример 1. Составьте РКС для формулы :

Решение.

Данной формуле соответствует следующая П–схема:

Пример 2.Найдите функции проводимости следующих релейно-контактных схем:

Решение.

Для П–схемы

соответствующая формула алгебры логики имеет вид:

L()()()

 

Упростим эту формулу следующим образом:

L(())(())

(()())

Последней формуле соответствует П-схема:

Пример 3.Построить РКС для F(x,y.z), если известно, что:

1. F(1,1,0) = F(0,0,0) = F(1,0,0) = 1

Решение.

Используя СДНФ (также можно использовать СКНФ), найдём сначала аналитическое выражение для функции F проводимости исходной схемы:

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

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

Пример 4.

Какой контакт необходимо вставить в вакантное место релейно-контактной схемы, чтобы функция проводимости полученной схемы стала бы равна данной булевой функции (если это возможно):

F(x, y) =

Решение.

Обозначим неизвестный контакт через @ и найдём аналитическое выражение для функции F проводимости исходной схемы:

Максимально упрощая это выражение получим:

Очевидно, что .

Решение логических задач

научить человека мыслить. Т.Эдисон

Пример 5.

Внимание Андрея, Дениса и Марата привлек пром­чавшийся мимо них автомобиль.

— Это английская машина марки "Феррари", — ска­зал Андрей.

— Нет, машина итальянская, марки "Понтиак", — возразил Денис.

— Это "Сааб", и сделан он не в Англии, — сказал Марат.

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

Какой же марки этот автомобиль и в какой стране изготовлен?

Решение.

Введем обозначения для логических высказываний:

А — машина английская;

И — машина итальянская;

П — это "Понтиак";

С — это "Сааб";

Ф — это "Феррари".

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

А ×`Ф v`А × Ф; И ×`П v`И × П; А ×`С v А × С.

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

(А ×`Ф v `А × Ф) × (И ×`П v`И × П) × (`А ×`С v А × С).

Для решения задачи нужно определить, при каких значениях логических переменных А, И, Ф, П и С это высказывание истинно.

Упростим высказывание, учитывая те обстоятельства, что машина не может быть одновременно и английской, и италь­янской (А × И = 0), а также не может одновременно иметь два разных названия (Ф × С = 0; Ф × П = О; П × С = О):

(А ×`Ф v`А × Ф) × (И ×`П v`И × П) × (`А ×`С v А × С) = А ×`Ф × И ×`П ×`А ×`С v А ×`Ф × И ×`П × А × С v А ×`Ф ×`И × П ×`А ×`С v А × Ф × И × П × А × С v А ×`Ф ×`И × П × А × С v`А × Ф × И ×`П × `А ×`С v`А × Ф × И ×`П × А × С v`А × Ф ×`И × П ×`А ×`С = О v О v О v О v`А × Ф × И ×`П ×`А × С v О v О v О =`А × Ф × И ×`П ×`С.

Высказывание`А × Ф × И ×`П ×`С истинно только при И = 1, Ф = 1, А = 0, П = 0, С = 0.

Ответ. Машина итальянская, марки "Феррари".

7.2.2 Решение логических задач табличным способом

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

Пример 6.

В симфонический оркестр приняли на работу трёх музыкантов: Брауна, Смита и Вессона, умеющих играть на скрипке, флейте, альте, кларнете, гобое и трубе.

Известно, что:

· Смит самый высокий;

· играющий на скрипке меньше ростом играющего на флейте;

· играющие на скрипке и флейте и Браун любят пиццу;

· когда между альтистом и трубачом возникает ссора, Смит мирит их;

· Браун не умеет играть ни на трубе, ни на гобое.

На каких инструментах играет каждый из музыкантов, если каждый владеет двумя инструментами?

Решение.

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

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

Из условия 4 следует, что Смит не играет ни на альте, ни на трубе, а из условий 3 и 5, что Браун не умеет играть на скрипке, флейте, трубе и гобое. Следовательно, инструменты Брауна — альт и кларнет. Занесем это в таблицу, а оставшиеся клетки столбцов "альт" и "кларнет" заполним нулями:

	скрипка	флейта	альт	кларнет	гобой	труба
Браун
Смит
Вессон

 

Из таблицы видно, что на трубе может играть только Вессон.

Из условий 1 и 2 следует, что Смит не скрипач. Так как на скрипке не играет ни Браун, ни Смит, то скрипачом является Вессон. Оба инструмента, на которых играет Вессон, теперь определены, поэтому остальные клетки строки "Вессон" можно заполнить нулями:

	скрипка	флейта	альт	кларнет	гобой	труба
Браун
Смит
Вессон

 

Из таблицы видно, что играть на флейте и на гобое может только Смит.

	скрипка	флейта	альт	кларнет	гобой	труба
Браун
Смит
Вессон

Ответ: Браун играет на альте и кларнете, Смит — на флейте и гобое, Вессон — на скрипке и трубе.

 

7.2.3 Решение логических задач с помощью рассуждений

Этим способом обычно решают несложные логические задачи.

Пример 7.

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

Решение.

Имеется три утверждения:

• Вадим изучает китайский;
• Сергей не изучает китайский;
• Михаил не изучает арабский.

Если верно первое утверждение, то верно и второе, так как юноши изучают разные языки. Это противоречит условию задачи, поэтому первое утверждение ложно.

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

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

Ответ: Сергей изучает китайский язык, Михаил — японский, Вадим — арабский.

Проверочная работа № 4

  Ι.Составьте РКС для следующих формул: 1.

Задача № 1.

Кто не пришел к кинотеатру?

Задача № 2.

Во всех же остальных предположениях. Оба имени названы неправильно. Кто принес цветы?

Задача № 3.

Как-то утром класс оказался плохо убранным. Ребята начали перебирать наиболее вероятные варианты. Было высказано семь различных предположений: дежурили Сергей и Даша, Даша и Андрей, Борис и Даша, Галя и Борис, Борис и Володя, Володя и Галя, Коля и Володя.

Кто дежурил в классе?

Задача № 4.

Помогите девочкам восстановить истину.

Задача № 5.

Сколько учителей будет в объединении, сколько различных специальностей они будут представлять?

Задача № 6.

Петров и Иванов никогда не держали в руках малярной кисти. Петров и Борисов живут в одном доме со штукатуром. Андреев и Петров подарили электрику красивую вазу. Борисов и Петров помогали плотнику строить гараж .

Борисов и Сидоров по субботам встречаются у электрика, а штукатур по воскресеньям приходит в гости к Андрееву.

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

Задача №7.

В сберкассе работают три человека: заведующий, кассир и контролер. Их фамилии: Борисов, Иванов, Семенов. Удалось установить, что кассир не имеет ни братьев, ни сестер и меньше всех ростом. Известно также, что Семенов женат на сестре Борисова и ростом выше контролера.

Можно ли по этим данным установить, кто есть кто?

Задача № 8.

В заметке было написано, что Иван, Андрей и Борис стали учителями. Теперь они живут тоже в разных городах: Минске, Витебске и Харькове. В заметке было еще написано, что первоначальные планы осуществились не полностью: Иван работает не в Минске, Андрей - не в Витебске; житель Минска преподает не математику, Андрей преподает не физику. Повезло только жителю Витебска: он преподает любимую им химию.

Кто есть кто?

Задача №9.

Однажды весной мы прочитали в газете интересное объявление, что в воскресенье в университете будет день открытых дверей. Весь класс отправился на… Возникает вопрос: кто есть кто?

Задача № 10.

Летом мы часто бывали на озере. Там каждый день устраивались гонки на моторных лодках. Самыми быстрыми были четыре лодки: «Дельфин», «Кит», «Волна»,… В первом заезде Борис плыл на лодке Сергея. Во втором заезде Сергей плыл на… Кому же из них какая лодка принадлежала?

Задача № 11.

Недалеко от нашего дома строился четырех квартирный дом. Когда строительство было закончено, и жильцы въехали в дом, у подъезда был вывешен список жильцов. Таким образом, мы узнали, что в этом доме живут Воронов, Павлов, Синицын, и Журавлев. Учительница сказала нам, что один из них – математик, другой – художник, третий – писатель, а четвертый – баянист. Но у кого из них какая фамилия, она не знала.

Мы решили это выяснить.

Задача № 12.

Арташ не играет ни в волейбол, ни в баскетбол. Отар играет в футбол и играет в волейбол. Тот из ребят, который играет волейбол, любит ходить в кино,… У кого какое спортивное занятие и любимое занятие.

Задача № 13.

Кто из них на каком факультете учится?

Задача № 14.

Кто из мальчиков в какую секцию ходит?

Задача №15.

Кто же из детей, где живет?

Задача № 16.

Кто эти люди по профессии и где их место жительства?

Задача № 17.

У кого из студентов какое имя и на каком курсе он учится?  

Задача № 18.

Кто же кем работает?

Задача № 19.

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

Задача № 20.

Кто из девочек на каком инструменте играет?  

Контрольная работа

То, что я понял, прекрасно, из этого я заключаю, что остальное, чего я не понял, тоже прекрасно.

Задача №1.

Антон сказал: "Моя собака – Рекс, а собака Петра – Кайма". Борис сказал: "Рекс – моя собака, а собака Виктора – Джек". Петр… Кто же на самом деле хозяин каждой из собак?

Задача №2.

Инструкция по выявлению неисправных узлов такова: 1) если неисправен хотя бы один из узлов компьютера, то горит по крайней мере… 2) если неисправен узел а, но исправен узел с, то загорается лампочка у;

Задача №3.

– Это мог сделать только или Витя, или Толя – сказал Андрей. – Я окно не разбивал, - возразил Витя, – и Коля тоже. – Вы оба говорите неправду, – заявил Толя.

Задача №4.

– Витя не ставил кляксу, – сказал Алёша, – это сделал Боря. – Ну, а ты что скажешь? – спросила Борю бабушка. – Это Витя поставил кляксу, – сказал Боря. – А Алёша не пачкал скатерть.

Задача №5.

P) если А не едет в Москву, то С не едет в Пятигорск; Q) если В не едет ни в Москву, ни в Ташкент, то А едет в Москву; R) если С не едет в Ташкент, то В едет в Киев;

Задача №6.

1) «Кажется, первым был Адамов, а вторым – Дронов»; 2) «Нет, на первом месте был Ершов, а на втором – Глебов»; 3) «Вот так болельщики! Ведь Глебов был на третьем месте, а Белов – на четвёртом!;

Задача №7.

1) С и Р не могут дежурить в первый вечер в связи с командировкой; 2) Если С выйдет во второй вечер или Р – в третий, то Е сможет подежурить в… 3) Если А н будет дежурить в третий вечер, то Е согласен дежурить во второй вечер;

Задача №8.

Задача №9.

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

Задача №10.

1. В первом заезде Борис был на лодке Виктора, а во втором Виктор на лодке Олега. 2. Пётр выиграл третий заезд на своей лодке «Мотылёк», при чём он выиграл и… 3. На «Колибри» во втором заезде плыл Олег, а в четвёртом плыл Борис.

Задача №11.

1. Девушка, которая играет на гитаре, говорит по-испански. 2. Люда не играет ни на скрипке, ни на виолончели и не знает английского… 3. Маша не играет ни на скрипке, ни на виолончели и не знает английского языка.

Задача №12.

прозаика и драматурга. Это были Алексеев, Борисов, Константинов и Дмитриев. Когда поезд тронулся, они углубились в чтение. Оказалось, что каждый из…

Задача №13.

Вскоре Ходже стало ясно, как зовут каждого из четырёх. Он заметил также, что не было языка, который был бы известен всем четырём, но каждый знал два… Самый младший из четырёх, Салал, не знал персидского языка, но был… Ни Салал, ни Абдул, ни Юсуф ни знали такого языка, на котором могли бы объясняться все трое между собой. Среди этих…

Задача №14.

Необходимые данные для решения этого вопроса можно получить из следующих 15 утверждений: 1. В ряд стоят 5 домов. 2. Англичанин живёт в красном доме.

Задача №15.

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

1. вода и молоко не в бутылке,

2. сосуд с лимонадом стоит между кувшином и сосудом с квасом,

3. в банке не лимонад и не вода,

4. стакан стоит около банки и сосуда с молоком.

Куда налита каждая жидкость?

Задача №16.

При построении восемь мальчиков разместились так, что:

1. А был впереди Б и В,

2. Б – впереди К через одного,

3. Л – впереди А, но после Д,

4. В после Е через одного,

5. Д между Б и Г,

6. Е рядом с К, но впереди В.

В каком порядке выстроились мальчики?

Задача №17.

Волейбольные команды А, Б, В, Г, Д и Е разыгрывали первенство. Известно, что команда А отстала от Б на три места, команда В оказалась между Г и Д, команда Е опередила Б, но отстала от Д. Какое место заняла каждая из команд?

Задача №18.

В семье четверо детей. Им 5, 8, 13, 15 лет. Детей зовут Аня, Боря, Вера и Галя. Сколько лет каждому ребёнку, если одна девочка ходит в детский сад, Аня старше Бори и сумма лет Ани и Веры делится на три.

Задача №19.

Четверо мальчиков Алёша, Ваня, Боря и Гриша соревновались в беге. После соревнований каждого из них спросили, какое место он занял. Ребята дали следующие ответы:

1. Алёша: «Я не был ни первым, ни последним».

2. Боря: « Я не был первым».

3. Ваня: «Я был первым».

4. Гриша: «Я был последним».

Трое из этих ответов правильны, а один – нет. Кто сказал правду, кто был первым?

Задача №20.

На острове живут два племени: аборигены и пришельцы. Аборигены всегда говорят правду, а пришельцы всегда лгут. Путешественник, приехавший на остров, нанял островитянина в проводники. Они пошли и увидели другого островитянина. Путешественник послал проводника узнать, к какому племени принадлежит этот туземец.

Проводник вернулся и сказал: «Туземец говорит, что он абориген».

Кем был проводник: пришельцем или аборигеном.

ЛИТЕРАТУРА

 

1. Градштейн И. С. Прямая и обратная теоремы. Элементы алгебры логики. – 5-е изд. – М.: Изд-во «Наука», 1972. – 128с.

2. Гиндикин С. Г. Алгебра логики в задачах. – М.: Изд-во «Наука», 1972. – 288с.

3. Зияитдинов Р.Г. Решение логических задач: Учеб. Пособие – 2-е изд., перераб. и доп. – Тверь: Твер. Гос. ун-т 2004. – 144с.;ил.

4. Ивлев Ю.В. Логика. – М.: Логос, 1997. – 272 с.

5. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов: Учебное пособие для ВУЗов. – М.: Академия, 2005. – 302 с.

6. Игошин В.И. Математическая логика и теория алгоритмов. – Саратов: Изд-во Саратов. Ун-та, 1991. – 256 с.

7. Колмогоров А.И., Драгалин А.Г. Введение в математическую логику. – М.: Изд-во Моск. Ун-та, 1982. – 120с.

8. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – 5-е изд., исправл. – М.:ФИЗМАТЛИТ, 2003. – 256с.

9. Лихтарников Л.М. Сто логических задач. Методические рекомендации для учителей математики школ. – В.Новгород: Новгород. Гос. пед. ин-т, 1990. – 111с.

10. Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник–практикум и решения. – СПб.: Издательство «Лань», 1999. – 288 с.

11. Никольская И.Л. Знакомство с математической логикой. М.: Московский психолого-социальный институт: Флинта, 1998. – 128 с.

12. Шапорев С.Д. Математическая логика. Курс лекций и практических занятий. – СПб.: БХВ-Петербург 2005. – 416 с.

 

Содержание

 

ВВЕДЕНИЕ. 3

1. ВЫСКАЗЫВАНИЯ И ЛОГИЧЕСКИЕ ОПЕРАЦИИ НАД НИМИ. ФОРМУЛЫ АЛГЕБРЫ ЛОГИКИ. ТАБЛИЦЫ ИСТИННОСТИ.. 4

1.1 Понятие высказывания. 4

1.2 Логические операции над высказываниями. 5

1.3 Формулы алгебры логики. 7

1.4 Решение типовых задач. 9

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

2 РАВНОСИЛЬНЫЕ ФОРМУЛЫ АЛГЕБРЫ ЛОГИКИ. РАВНОСИЛЬНЫЕ ПРЕОБРАЗОВАНИЯ ФОРМУЛ.. 21

2.1 Три группы равносильностей. 21

2.2 Равносильные преобразования формул. 22

2.3 Примеры решения задач. 23

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

3 ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ. СОВЕРШЕННЫЕ НОРМАЛЬНЫЕ ФОРМЫ. ПРОБЛЕМА РАЗРЕШИМОСТИ.. 28

3.1 Функии алгебры логики. 28

3.2 Представление произвольной функции алгебры логики в виде формулы алгебры логики. 31

3.3 Совершенные нормальные формы алгебры логики. 33

3.3.1 Дизъюнктивная нормальная форма и совершенная дизъюнктивная нормальная форма (ДНФ и СДНФ) 33

3.3.2 Конъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма (КНФ и СКНФ) 34

3.4 Проблема разрешимости. 36

3.5 Примеры решения задач. 38

Проверочная работа № 3. 45

§ 7. Некоторые приложения алгебры логики. 48

7.1 Приложения алгебры логики в технике (релейно-контактные схемы) 48

7.2 Решение логических задач. 54

7.2.1 Решение логических задач средствами алгебры логики. 55

7.2.2 Решение логических задач табличным способом. 56

7.2.3 Решение логических задач с помощью рассуждений. 58

Проверочная работа № 4. 60

Контрольная работа. 72

ЛИТЕРАТУРА.. 92

 

 

учебное издание

АЛГЕБРА ЛОГИКИ

    Составители: