Методические указания к выполнению практических работ по дисциплине ЕН.02 «Элементы математической логики» по специальности 09.02.03 «Программирование в компьютерных системах»

ТАМБОВСКОЕ ОБЛАСТНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

«ПРОМЫШЛЕННО-ТЕХНОЛОГИЧЕСКИЙ КОЛЛЕДЖ»

Е.А. Шмакова

Методические указания

к выполнению практических работ

по дисциплине ЕН.02 «Элементы математической логики»

по специальности 09.02.03 «Программирование в компьютерных системах»

Мичуринск 2020

ЛИСТ СОГЛАСОВАНИЯ

Методические указания для проведения практических работ по дисциплине «Элементы математической логики» разработаны для специальности 09.02.03 «Программирование в компьютерных системах» в соответствии с требованиями Федерального государственного образовательного стандарта среднего профессионального образования, утвержденного Приказом Министерства образования и науки РФ от 13.08.2014г. №350.

Методические указания рассмотрены и одобрены на заседании предметной (цикловой) комиссии по специальности 09.02.03 «Программирование в компьютерных системах» ТОГАПОУ «Промышленно-технологический колледж» (протокол № 10 от 29.05.17 г.).

Организация-разработчик:

Тамбовское областное государственное автономное профессиональное образовательное учреждение «Промышленно-технологический колледж».

Разработчик:

Шмакова Е.А. – преподаватель ТОГАПОУ «Промышленно-технологический колледж»

СОГЛАСОВАНО:

Директор «ЦИТ»

_______________К. Горлов

АННОТАЦИЯ

Методические указания для проведения практических работ предназначены для контроля и оценки результатов освоения дисциплины ЕН.02 «Элементы математической логики».

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

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

Методические указания разработаны на основании ФГОС СПО по специальности 09.02.03 «Программирование в компьютерных системах»», программы учебной дисциплины ЕН.02 «Элементы математической логики».

ОГЛАВЛЕНИЕ

Раздел 2 Основы теории множеств Тема 2.1. Множества	5
Практическая работа №1 Тема: « Операции над множествами»	13
Раздел 3. Алгебра логики Тема 3.1 Логические операции	13
Практическая работа № 2 Тема: « Формулы алгебры высказываний, их основные виды и истинности значения.»	18
Тема 3.2. Законы логики. Упрощение формул логики с помощью равносильных преобразований
Практическая работа № 3 Тема: «Законы и равносильность формул алгебры высказываний».	23
Практическая работа № 4  Тема: «Приведение функций к ДНФ и КНФ»	23
Раздел 4. Булевы функции Тема 4.1. Способы задания булевых функций	24
Практическая работа №  5 Тема: «Решение задач по алгебре логики»	30
Практическая работа № 6, 7 Тема: «Важнейшие замкнутые классы. Функционально-полные системы».	36
Практическая работа 8 Тема: «Решение задач по теме «Логические рассуждения».	36
Раздел 6. Предикаты. Исчисление предикатов Тема 6.1. Предикаты	37
Практическая работа №9 Тема: «Непротиворечивость и полнота исчисления предикатов».	40
Раздел 7. Элементы теории автоматов. Тема 7.1. Базовые множества для автоматов.	41
Практическая работа. №10. Тема: « Решение задач по теории автоматов.»	42

Теоретические сведения и рекомендации

по выполнению практической работы

Раздел 2 Основы теории множеств

Тема 2.1. Множества

Под множеством понимается совокупность некоторых объектов. Эти объекты, предметы называются элементами множества. Множества будем обозначать А, В, С,…, или А₁, А₂,… Если множество состоит из конечного числа элементов, то оно называется конечным. Например, множество студентов в группе конечное. Если количество элементов множества бесконечное, то оно называется бесконечным. Например, множество всех натуральных чисел бесконечное. Множество всех прямых, проходящих через одну точку на плоскости, бесконечное.

Конечному множеству относятся множество, не содержащее ни одного элемента (пустое множество).  Число  элементов пустого множества равно нулю .

Если элемент х принадлежит множеству  А, то  ;  если нет-то  .

Определение 1.  Если каждый элемент множества А есть элемент множества В, то А является частью или подмножеством множества В:  при этом .

В частности, , если А=В, т.е. множество А есть подмножество самого себя. Кроме того, пустое множество есть часть всего множества. Множество А и пустое множество называются несобственными подмножествами множества А, все остальные называются собственными. Если множество содержит  элементов, то подмножеств будет .

Определение 2. Суммой (объединением) двух множеств А и В называется множество, элементы которого принадлежат хотя бы к одному из множеств. Обозначаются   .

Если множеств несколько, то имеем 

Объединение множеств  А  и  В  можно изобразить диаграммой Эйлера – Венна.

                                               

Определение 3. Произведением (пересесечением) двух множеств А и В называется множество, элементами которого являются общие элементы обоих множеств:

                                               

Если множеств несколько, то запишем   .

Определение 4. Разностью множеств А и В называется множество тех элементов множества А, которые не суть элементы множества В:  А \ В.

Определение 5.   Дополнением      множества    называется  

 .

Свойства

1. Коммутативность: ;
2. Ассоциативность:

,

;

3. Дистрибутивность (пересечения относительно объединения)

.

В общем случае

     

      ,

      ,

      .

Очевидны  следующие  соотношения двойственности (сложения и пересечения).  Для любой (конечной или бесконечной) системы подмножеств А_j   данного произвольного множества Х  имеет место тождества

.

Последовательность множеств   М₁, М₂, … , М_n, … называется убывающей (возрастающей), если для любого    имеем   .

Замечание.   Пересечение (сумма) любой бесконечной подпоследовательности совпадает с пересечением (суммой) всей последовательности.

        Сумма разностей множеств: 

                             

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

Замечания:   1) Относительно двух эквивалентных множеств говорят, что они имеют одинаковую мощность.

                         2) Два конечных множества эквивалентны тогда и только тогда, когда они состоят из одного и того же конечного числа элементов.

                         3) Если     . 

                         4) Мощность -  это то, что есть общего у всех эквивалентных между собой множеств.

Если множество конечное, то мощность конечного множества равна количеству элементов этого множества.

Таким образом, мощность конечного множества есть конечное число.

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

Таким образом, счетное множество это такое множество А, все элементы которого могут быть занумерованы в бесконечную последовательность: а₁, а₂, …, а_n, так, чтобы каждый элемент получил лишь один номер “n” и, обратно, каждое натуральное число “n” было бы в качестве номера дано одному и лишь одному элементу множества.

Бесконечное множество, не являющееся счетным, называется несчетным множеством.

Взаимно однозначное соответствие между двумя множествами является частным случаем общего понятия отображения: если каким–то образом каждому элементу “х” некоторого множества Х поставлен в соответствие определенный элемент “y” некоторого множества У, то говорят, что имеется отображения множества Х во множество У, или f, аргумент который изображает множество Х, а значения принадлежат множеству У: и пишут .

Ø  Мощность счетного множества равна бесконечности;

Ø  Мощность несчетного множества имеет континуум;

Например,  мощность множества чисел отрезка [0, 1].

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

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

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

Например, множество (0, 1) (М), верхняя грань имеет . Если М=(0, 1], то .

Теперь пусть дано непустое множество М, ограниченное снизу. Тогда называется  нижней гранью множества М. Обозначается   .

Например:  М=(3; 4],  inf .

Примеры:

1) Определить множество А решений уравнения х² – 25 = 0.

Решение:  А = { х | х²  - 25 = 0 } = { -5; 5 }.

2) Определить множество В решений неравенства 2х + 9  0.

Решение:  В = { х | 2х + 9  0 } = { х | х  -4,5 } = [ -4,5; ∞).

3) Заданы множества А = { 1; 3; 4; 6 } и В = { 3; 5; 6; 7 }. Определить результаты   операций   АВ,  АВ,  А\В,  В\А,  А+В.

Решение:

А + В = (А\В)  (В\А)

диаграмма   Эйлера-Винна.

АВ = { 1; 3; 4; 5; 6; 7 };

АВ = { 3; 6 };

А\В = { 1; 4 };

В\А = { 5; 7 };

А + В = { 1; 4; 5; 7 }.

4) Определить результаты тех же операций,  если А = { х |  1  х  5 },                                                                                      В = { х | 3  х < 7 }.

Решение:

   АВ = { х | 3  х  5 } = [ 3; 5 ];

   АВ = { х | 1  х < 7 } = [ 1; 7 );

   А\В = { х | 1  х < 3 } = [ 1; 3 );

   В\А = { х | 5 < х < 7 } = ( 5; 7);

   А + В = { х | 1  х < 3 5 < 4 < 7 } = [ 1; 3)  ( 5; 7).

5) Доказать  формулу  В(А\В) = АВ.

Решение:  Рассмотрим диаграммы

      А\В:

В  (А\В):

Результат для правой части:

 

АВ:

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

6) Найти все подмножества множества А = { 0; 1; 3 }.

Решение:  Несобственные подмножества Ø и А; одноэлементные {0}, {1}, {3}; двухэлементные {0; 1}, {0; 3}, {1; 3}. Следовательно, степень множества Р(А), т.е. множество всех подмножеств, имеет вид  Р(А) = {Ø; {0}; {1}; {3}; {0; 1}; {0; 3}; {1; 3}; {0; 1; 3}}.

Проверка: если множество А состоит из ″n″ элементов, то число всех его подмножеств равно .

В нашем случае, n = 3. Значит, 2³ = 8, что совпадает с числом объектов в Р(А).

7) Оценить множество  А = {2; 6; 1; 8}.

Решение:  max А = 8,  min A = 1,   sup A = 8,   inf A = 1.

8) Оценить множество  N = {1; 2; 3; …}, т.е. натуральный ряд.

Решение:  min N = 1, max N – не существует, sup N – не существует, inf N = 1.

9) Оценить множество А = { х | 2 ≤ х < 5 }.

Решение:  

 

min А = 2,  max A –не существует, т.к. 5А,  sup A = 5,  inf A = 2.

10)  Оценить множество А = { х | 3 < х < 8 }

Решение:  

 

min A – не существует, т.к. 3А,   max А – не существует,

inf A = 3,    sup A = не существует (sup A  = ∞).

Практическая работа №1

Тема: « Операции над множествами»

Теоретическая часть:

1.1.        Что такое множество?

1.2.        Перечислите операции над множествами

1.3.        Что такое мощность множества?

Практическая часть:

1) Изобразить множества А-«растение», В-«цветок», С-«роза» с помощью кругов Эйлера.

2) Доказать тождество, используя только определения операций над множествами

               

3) Считая, что   упростить  выражение

4) Задайте характеристическим свойством множество всех прямоугольных треугольников.

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

6) Даны отрезки  Найдите множество и изобразите кругами Эйлера

Раздел 3. Алгебра логики

Тема 3.1 Логические операции

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

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

Учение о высказываниях называется алгеброй высказываний и является первой из формальных логических теорий.

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

Например,   1)  Москва столица России – истинно;

                2)  5 >10 – ложно.

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

Например, геометрической фигурой называется любое множество точек; был звонок? Высказывания будем обозначать буквами А, В, … или X, Y, Z, … или p, q, ..

Их значения, т.е, истину или ложь, будем обозначать И и Л, или 1 и 0. Будем рассматривать только такие высказывания, величины, принимающие значения

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

“не”, “и”, “или”, “если … , то”.

Определение 1.  Отрицание.

Каждому высказыванию Х можно сопоставить утверждение, заключающееся в том , что Х ложно. Обозначается .

Если Х – истинно, то - ложно или если Х – ложно, то  - истинно.

Например,   2 > 3 – ложно, то  - истинно;

                     2+3=5 – истинно, то  - ложно.

Пусть 0 – означает ложно, а 1 – истинно.

Тогда можно составить таблицу истинности:

Х
1	0
0	1

Определение 2. Высказывания, составленные из данных высказываний Х и У при помощи слова “И” называют произведением (конъюнкцией) высказываний и обозначают  & .  Конъюнкция Х^У истинна в том и только в том случае, когда высказывания Х и У истинны.

Например,   х: 2<3  и  у: 3<4, то  Х^У:  2< 3< 4.

Высказывание  Х^У  в данном случае истинно, т.к. истинны оба высказывания Х и У.

Двойное неравенство   3< 4< 2  – ложно, т.к.  3< 4 – истинно,  то  4< 2 – ложно.

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

Х	У	Х^У
0	0	0
0	1	0
1	0	0
1	1	1

Определение 3.  Высказывания, составленные из данных высказываний Х и У при помощи слова “или”, называют суммой (дизъюнкцией) высказываний и обозначают   Х+У   или   ХÚУ.

Сумма высказываний истинна тогда и только тогда, когда истинно хотя бы одно из данных высказываний.

Например,  Х: завтра первая пара сопромат и У: завтра первая пара математика. Тогда ХÚУ: завтра первая пара сопромат или математика истинно, если действительно завтра будет первой парой сопромат или математика.

Таблица истинности:

Х	У	ХÚУ
0	0	0
0	1	1
1	0	1
1	1	1

Определение 4.  Высказывания составленные из данных высказываний Х и У при помощи слова “если …, то”, называют импликацией и обозначают Х®У. Высказывание Х – условие (посылка), У – заключение (следствие). Импликация Х®У считается ложным высказыванием только в том случае, когда условие (высказывание Х) истинно, а заключение (высказывание У) ложно.

Например,  если число 24 делится на 2 и 3, то оно делится на 7 ложно. Если Х – условие не верно, то Х®У истинно, т.к. из не верного условия вытекает все, что угодно.

Пример:   Если  2 >  3,  то 5 > 6 – истинно.

Таблица истинности:

Х	У	Х®У
0	0	1
0	1	1
1	0	0
1	1	1

Если посылка Х и импликация Х®У истинны, то истинно и заключение У. В этом случае пишут  ХУ  и  говорят, что из Х следует У.

Определение 5.  Х~У есть высказывание, истинное тогда и только тогда, когда Х и У оба истинны или оба ложны. Это высказывание называется эквивалентностью (Х эквивалентно У).

Х	У	Х~У
1	1	1
0	1	0
1	0	0
0	0	1

Таблица истинности:

1)            Х~ У= (Х^Y) Ú ;

2)            Х~ У= (Х®У) ^ (У®Х).

Алгоритм построения таблиц истинности для сложных выражений:

1. Определить количество строк:

количество строк = 2ⁿ + строка для заголовка,

n - количество простых высказываний.

2. Определить количество столбцов:

количество столбцов = количество переменных + количество логических операций;

• определить количество переменных (простых выражений);
• определить количество логических операций и последовательность их выполнения.
2. Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности с учетом таблиц истинности основных логических операций.

Пример: Составить таблицу истинности логического выражения:

D = ¬ А & (B  C).

Решение: 

1. Определить количество строк:

на входе три простых высказывания: А, В, С поэтому n=3 и количество строк = 2³ +1 = 9.

2. Определить количество столбцов:
• простые выражения (переменные): А, В, С;
• промежуточные результаты (логические операции): 
  ¬ А - инверсия (обозначим через E); 
  B  C - операция дизъюнкции (обозначим через F); 
  а также искомое окончательное значение арифметического выражения: 
  D = ¬ А & (B  C). т.е. D = E & F - это операция конъюнкции.
3. Заполнить столбцы с учетом таблиц истинности логических операций.

A	B	C	E	F	E & F
0	0	0	1	0	0
0	0	1	1	1	1
0	1	0	1	1	1
0	1	1	1	1	1
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	0	1	0
1	1	1	0	1	0

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

Некоторые свойства равносильности:

  равносильно  Х;

Х ^ X  равносильно  X;                                      

X Ú X  равносильно  X;                                      

  равносильно  Y;

  равносильно   .

  истинно,   ложно.

Пример:  Доказать равносильность   х ~ у = .

Решение: 

х ~ у =

         .

Практическая работа № 2

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

Теоретическая часть

1)      Что такое высказывание?

2)      Перечислите логические операции

3)      Основные логические  операции

Практическая часть

2.1. Определите значения истинности следующих высказываний:

а) Санкт-Петербург расположен на Неве и 2 + 3 = 5;

б) 7 — простое число и 9 — простое число;

в) 7 — простое число или 9 — простое число;

г) Число 2 четное или это число простое;

е) 2-2 = 4 или белые медведи живут в Африке;

ж) 2-2 = 4, и 2-2<5, и 2-2>4;

з) 2 — рациональное число или -5 — иррациональное число;

и) Фобос и Луна — спутники Марса;

к) 3*3 = 9 и 4 + 7=11.

2.2. Пусть через А обозначено высказывание «Этот треугольник равнобедренный», а через В — высказывание «Этот треугольник равносторонний». Прочитайте следующие высказывания:

1)

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

1) Если в треугольнике любая его медиана не является высотой и биссектрисой, то этот треугольник не равнобедренный и не равносторонний.

2.4.Являются ли формулы эквивалентными?.

1) f(x,y,z)=((z │ x)&(zy))  ((zVx)(zVy)) и

g(x,y,z)=((x│y) │ (yz))&((zx)&(zy))

2)  f(x,y,z)=((xy) (yz))  ((zx)│(z&y)) и

g(x,y,z)=((xz)&(yVx)) ((y&x) (x│z))

2.5.Являются ли данные формулы тавтологией?

1)(X Y) (X Y)
2)(X Y) & (Y X) (X Y)

2.6.Переведите на язык логических выражений следующие высказывания:

1)        «Я поеду в Москву, и если встречу там друзей,  то мы интересно проведем время».

2)        «Если будет солнечная погода, то ребята пойдут в лес, а если будет пасмурная погода, то ребята пойдут в кино».

3)        «Неверно, что если дует ветер, то солнце светит только тогда, когда нет дождя».

Тема 3.2. Законы логики.

Упрощение формул логики с помощью равносильных преобразований

Свойства логических операций

Порядок выполнения логических операций

1.                        (   )

2.                        инверсия (отрицание)    

3.                        конъюнкция( логическое умножение)  , в остальных случаях=0)

4.                        а) дизъюнкция (логическое сложение)  , в остальных случаях=1)

    б) неравнозначность (либо…  либо)   в остальных случаях=0)

5. а) импликация (если…., то), , в остальных случаях=1)

б)      эквивалентность (тогда и только тогда)  в остальных случаях=0)

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

1. Закон тождества		A=A
2. Вторая форма закона не противоречия
3. Закон исключения третьего
4.      Закон двойного отрицания
5.      Вытекает из 2 закона
6. Свойства констант
7.      Закон идемпотентности
8.      Закон коммутативности (переместительный закон)
9. Законы ассоциативности (сочетательный закон)
10. Закон дистрибутивности (распределительный закон)
11.   Законы поглощения
12 .Законы де Моргана
Правила замены операции импликации
14.   Правила замены операции эквивалентности
15. Формула склеивания
16. Правила замены операции неравнозначности

·         ПРИМЕРЫ УПРОЩЕНИЯ ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ

(списать, подписывая номера законов, разобраться в решении)

Упрощение логических выражений

Закон 11 (поглощения)

Примеры

Примеры

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

Пример: Упростить выражение

a)

b)

c)

d)

e)

f)

Пример:  Доказать, что Х®У = .

Решение:  .

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

Пример (Логическая задача):

На вопрос, кто из трех студентов изучал логику, был получен правильный ответ: если изучал первый, то изучал и второй, но не верно, что если изучал третий, то изучал и второй. Кто из студентов изучал логику?

Решение: Обозначим через Х₁, Х₂, Х₃ – высказывания, состоящие в том, что I, II, III студенты изучали логику. Из задачи следует истинность высказывания:

    , 

т.к.  - ложно.  Значит,  - ложно.

Из истинности S вытекает истинность    отсюда вытекает, что логику изучал третий студент, а первый и второй не изучали.

Практическая работа № 3

Тема: «Законы и равносильность формул алгебры высказываний».

1.    Теоретическая часть

1.2.Запишите законы булевой алгебры

1.3.Запишите равносильности формул алгебры высказываний

2.      Практическая часть

2.1.Доказать эквивалентность с помощью равносильных преобразований

a)      (A(A˅C)(B˅C)) ~ (AB˅AC);

b)      ((A˅B)˄(B˅C)˄(C˅D)) ~ (AC˅BC˅BD);

c)      ((AB˅C)˄(AC˅B)˄(BC˅A)) ~ (AB˅AC˅BC);

d)      ((A˅B˅C)˄(B˅C˅D)˄(C˅D˅A)) ~ (AB˅AD˅BD˅C)

2.2.По телевизору синоптик объявляет прогноз погоды на завтра и утверждает следующее:

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

2.           Если будет дождь, то будет пасмурно и без ветра.

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

Так какая же погода будет завтра?

Решить  задачу средствами алгебры логики.

Практическая работа № 4

Тема: «Приведение функций к ДНФ и КНФ»

1.             Теоретическая часть

1.1.       Что называется ДНФ?

1.2.       Что называется КНФ?

2.             Практическая часть

2.1.       Записать в КНФ

2.2.       Записать в ДНФ

2.3.       Составить таблицу истинности для булевой функции

a)            

b)     

c)     

d)     

2.4.       Опустите излишние скобки и упростите высказывание

((  С)

Раздел 4. Булевы функции

Тема 4.1. Способы задания булевых функций

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

Обычно используется следующая схема решения:

1. изучается условие задачи;
2. вводится система обозначений для логических высказываний;
3. конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;
4. определяются значения истинности этой логической формулы;

из полученных значений истинности формулы определяются значения истинности введённых логических высказываний

Пример 1:    За отсутствие документов наряд полиции задержал трёх студентов разных вузов: Романа, Сергея и Павла. На допросе каждый из них показал следующее:

        - Роман – я учусь в ЮрГУ, а Сергей – в ЧелГУ;

        - Сергей – я учусь в ЮрГУ, а Роман – в Торговом институте;

        - Павел – я учусь в ЮрГУ, а Роман – в ЧелГУ.

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

Решение: Обозначим через  Х_у студента, имя которого начинается с буквы Х, а у – первая буква названия института, в котором он учиться.

Т.к. в показаниях студентов одно утверждение верно, а другое – нет, то составим истинные дизъюнкции:

 Р_ю  С_Ч = 1,    С_ю Р_т = 1,   П_юР_ч  = 1.

Тогда конъюнкция этих дизъюнкций будет истинной:

Преобразуем первые двое скобок

,

,

,

.

Ответ:  Сергей учится в ЧелГУ,  Роман – в торговом институте,  Павел – в ЮрГУ.

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

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

Пример 2:   По подозрению в совершенном преступлении задержали Брауна, Джона и   Смита. Один из них был уважаемым в городе стариком, другой был малоизвестным чиновником, третий – известным мошенником. В процессе следствия старик говорил правду, мошенник лгал, а третий в одном случае говорил правду, а в другом – ложь. Их утверждения следующие:

Браун:  Я совершил это, Джон не виноват;

Джон:   Браун не виноват. Преступление совершил Смит;

Смит:   Я не виноват, виноват Браун.

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

Решение:  Введём обозначения:

Б – виноват Браун,  Д – виноват Джон,  С – виноват Смит.

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

,   ,   , из которых по условию задачи две ложны, а одна истинна.

Тогда    будет истинна.

Эта формула не тождественно истинна. Действительно, если истинно высказывание Д и ложны Б и С, то L = 0. Но эта формула не тождественно ложна. Например, при истинном высказывании Б и ложных высказываниях Д и С имеем  L = 1.

Составим таблицу истинности формулы L и проанализируем все случаи, когда L истинна:

	Б	Д	С				L
1	1	1	1	0	0	0	0
2	1	1	0	0	0	1	1
3	1	0	1	1	0	0	1
4	1	0	0	1	0	1	1
5	0	1	1	0	1	0	1
6	0	1	0	0	0	0	0
7	0	0	1	0	1	0	1
8	0	0	0	0	0	0	0

Отсюда верно, что формула L истинна в пяти случаях.

Случай 4 исключаем, т.к. оказываются истинны две конъюнкции, а это противоречит условию задачи.

В случаях 2,3,5 оказываются истинными по два высказывания Б и Д, Б и С, Д и С соответственно, что противоречит условию задачи.

Следовательно, справедлив случай 7, т.е. преступник – Смит. Он известный мошенник, и оба его высказывания ложны . При этом Б = 0, Д = 0, т.е. высказывания Б и Д ложны. Значит, истинна пара высказываний Джона, а у Брауна первое высказывание ложное, а второе – истинное. Отсюда вытекает, что Джон – уважаемый в городе старик, а Браун – малоизвестный чиновник.

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

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

1. Смит самый высокий;
2. играющий на скрипке меньше ростом играющего на флейте;
3. играющие на скрипке и флейте и Браун любят пиццу;
4. когда между альтистом и трубачом возникает ссора, Смит мирит их;
5. Браун не умеет играть ни на трубе, ни на гобое.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример 5. В поездке пятеро друзей — Антон, Борис, Вадим, Дима и Гриша, знакомились с попутчицей. Они предложили ей отгадать их фамилии, причём каждый из них высказал одно истинное и одно ложное утверждение:

Дима сказал: "Моя фамилия — Мишин, а фамилия Бориса — Хохлов". Антон сказал: "Мишин — это моя фамилия, а фамилия Вадима — Белкин". Борис сказал: "Фамилия Вадима — Тихонов, а моя фамилия — Мишин". Вадим сказал: "Моя фамилия — Белкин, а фамилия Гриши — Чехов". Гриша сказал: "Да, моя фамилия Чехов, а фамилия Антона — Тихонов".

Какую фамилию носит каждый из друзей?

Решение. Обозначим высказывательную форму "юноша по имени А носит фамилию Б" как А_Б, где буквы А и Б соответствуют начальным буквам имени и фамилии.

Зафиксируем высказывания каждого из друзей:

1. Д_М   и   Б_Х;
2. А_М   и   В_Б;
3. В_Т   и   Б_М;
4. В_Б   и   Г_Ч;
5. Г_Ч   и   А_Т.

Допустим сначала, что истинно Д_М. Но, если истинно Д_М, то у Антона и у Бориса должны быть другие фамилии, значит А_М и Б_М ложно. Но если А_М и Б_М ложны, то должны быть истинны В_Б и В_Т, но В_Б и В_Т одновременно истинными быть не могут.

Значит остается другой случай: истинно Б_Х. Этот случай приводит к цепочке умозаключений:
 
Б_Х истинно Б_М ложно В_Т истинно А_Т ложно Г_Ч истинно В_Б ложно А_М истинно.

Ответ: Борис — Хохлов

Практическая работа №  5

Тема: «Решение задач по алгебре логики»

Теоретическая часть:

1.      Как называется форма мышления, в которой что-либо утверждается или отрицается о реальных объектах, их свойствах и отношениях между ними?

2.      Как обозначается логическое высказывание?

3.      Какие значения может принимать логическая переменная?

4.      Назовите основные логические операции.

Практическая часть

Решите задачи:

1.        Виктор, Роман, Леонид и Сергей заняли на олимпиаде по информатике четыре первых места. Когда их спросили о распределении мест, они дали три таких ответа:

n  Сергей — первый, Роман — второй;

n  Сергей — второй, Виктор — третий;

n  Леонид — второй, Виктор — четвертый.

Известно, что в каждом ответе только одно утверждение истинно. Как распределились места?

2.        На деловой встрече были писатель, химик, биолог и врач. Их звали (по алфавиту): Анна, Дмитрий, Екатерина и Стас. Дмитрий сказал биологу, что только что встретил Екатерину с пончиками. Анна сидела напротив врача и рядом с химиком. Врач про себя размышлял о том, что Стас - глупое имя. Назовите специальность каждого.

3.        На парту Оли упал бумажный самолет с нарисованными красными сердечками. Оля развернула его и прочитала: "Ты - лучшая девочка в классе!" Она повернулась в сидящим за ней ребятам: Ивану, Сергею, Алексею.

- Кто из вас делает мне такие комплименты? - спросила Оля.
- Это Сергей! - сказал Иван.
- Я ничего такого не делал! - сказал Сергей.
- Не имею никакого отношения к этому самолётику! - сказал Алексей.
Подруга Оли Маша ухмыльнулась: "Двое из них лгут!" Однако она не хочет больше ничего говорить.
Кто является тайным поклонником Оли?

4.      В городе живут друзья: Иванов, Петренко, Сидорчук, Гришин, Капустин.

ИХ ПРОФЕССИИ: маляр, мельник, плотник ,почтальон, парикмахер.

 ИЗВЕСТНО ЧТО:

·       Петренко и Гришин никогда не держали в руках малярной кисти;

·       Иванов и Гришин давно собираются посетить мельницу, на которой работает их товарищ;

·       Петренко и Капустин живут в одном доме с почтальоном;

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

·       Иванов и Петренко каждое воскресенье играют в городки с маляром и плотником;

·       Гришин и Капустин по субботам встречаются в парикмахерской, где работает их друг, а почтальон предпочитает бриться сам.

КТО ЕСТЬ КТО?

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

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

Элементарные переключательные функции позволяют получить сложные функции от большего числа аргументов путем подстановки в данную функцию вместо ее переменных других функций. Такой метод получения функций называется суперпозицией. Например, имея элементарные функции двух переменных z₁ = x₁x₂ и z₂ = x₃x₄, можно получить функцию z₃ = x₁(x₃x₄), z₄ = x₃x₁x₂, зависящие от трех переменных.

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

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

Какими свойствами должны обладать функции системы S = {f_i(X)}, чтобы любая ПФ f(x₁, x₂, …, x_n) была представима в виде суперпозиции этой системы S.

Система S называется полной в P_k, если любая функция fP_k представима в виде суперпозиции этой системы.

Система S называется базисом, если полнота S теряется при удалении хотя бы одной функции, где P_k – k-значная логика.

Для установления полноты системы S булевых функций f_i(S в P₂) используют критерий полноты, сформулированный американским математиком Э.Л. Постом (1897–1954) и отечественным математиком С.В. Яблонским.

Определим предварительно 5 классов булевых функций.

1.     Класс функций, сохраняющих константу 0. В этот класс входят функции, которые на нулевом наборе переменных принимают нулевое значение: f(00…0) = 0.  Такова, например, конъюнкция f₈(00) = 0×0 = 0.

2.     Класс функций, сохраняющих константу 1. В этот класс входят функции, которые на единичном наборе переменных принимают единичное значение: f(11…1) = 1. Этим свойством также обладает конъюнкция f₈(11) = 1×1 = 1. Классы 1, 2 легко устанавливаются по таблице истинности.

3.     Класс самодвойственных функций. Переключательные функции f(x₁ x₂ …x_n) и g(x₁ x₂ …x_n) называют двойственными, если имеет место равенство f(x₁ x₂ …x_n) = , т.е. когда одна функция получается из другой, если провести замену всех переменных на их инверсии и провести инверсию функции. Например, f₈(x₁ x₂) = x₁ x₂  и f₁₄(x₁ x₂) = x₁  x₂ двойственны: . Это можно доказать, построив таблицу истинности (табл.1).

                                                                                               Таблица 1

Таблица истинности

x1	x2		x1x2
0	0	0	0
0	1	0	0
1	0	0	0
1	1	1	1

Переключательная функция называется самодвойственной, если она двойственна по отношению к самой себе: f(x₁ x₂ …x_n) = . Такова, например, функция f₁₀(x₁ x₂) = x₁:= x₁ = x₁.

Самодвойственность устанавливается по таблице истинности следующим образом: значения функции, симметричные относительно середины таблицы, инверсны. Например, для f₁₀(x₁ x₂) значения функции представляют собой вектор , каждый разряд которого является инверсным по отношению к симметричному разряду относительно середины, отмеченной пунктиром.

Эти разряды соответствуют инверсным наборам x₁ x₂: 00–11, 01–10. Самодвойственны функции: , , x₂, x₁.

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

Эта операция определяется таблицей истинности (табл. 2).

                                                                                 Таблица 2

Таблица истинности

a	b	ab
0	0	0
0	1	1
1	0	1
1	1	0

Тогда линейная функция имеет вид:

,

где c₀, c₁, c₂ – константы 0, 1.

Например, для функции f₆(x₁ x₂) = x₁x₂ при c₀ = 0, c₁ = c₂ = 1: f₆(x₁ x₂) = 01× x₁x₂.

Получим все линейные функции двух переменных, задав все возможные значения c₀ c₁ c₂ (табл. 3.).

Из табл. 3.16 видно, что каждая линейная функция имеет инверсную ей функцию: константа 0 – константа 1; повторение x₁, x₂ – инверсия ,; сложение по модулю 2 x₁  x₂ – эквиваленция .

Таблица 3.

Линейные функции двух переменных

c0	c1	c2	Вид полинома	Можно доказать, используя, например, таблицу истинности, что:
0	0	0	0
0	0	1	x2
0	1	0	x1
0	1	1	x1x2	=
1	0	0	1	–
1	0	1	1x2	=
1	1	0	1x1	=
1	1	1	1x1x2	==

5.       Класс монотонных функций. Монотонная функция на большем сравнимом наборе переменных принимает не меньшие значения. Это удобно проверять на решетках Хассэ. Так, для двух переменных решетка имеет вид, как на рис. 1

На рис. 3.5 проставлены значения монотонной функции x₁. Видно, что 11 > 01 > 00, 11 > 10 > 00 (частично упорядоченное множество наборов).

 

                                                                         Рис. 1. Решетка Хассэ для двух

                                                                          переменных с указанием значений

                                                                          f₁₀(x₁ x₂) = x₁

Очевидно, что константы 0, 1 – монотонные функции, дизъюнкция и конъюнкция – монотонные функции, повторения x₁, x₂ – монотонные функции.

Критерий полноты Поста – Яблонского

Система S булевых функций f_i является полной  тогда и только тогда, когда выполняются пять условий:

1)        существует  f_iS, несохраняющая константу 0;

2)        функция  f_iS, несохраняющая константу 1;

3)        нелинейная;

4)        несамодвойственная;

5)        немонотонная функция в системе S.

Рассмотрим пример анализа и определения свойств ПФ заданной десятичным номером 174₁₀  [4].

Дано: двоичная переключательная функция № 174₁₀.

Получим соответствующий двоичный код: 10101110₂ (2⁷ + 2⁵ + 2³ + 2² + 2¹). Таблица истинности ПФ № 174₁₀ показана в табл. 4.

                                                                                                         Таблица 4

Таблица истинности

Переменные			ВС	f(abc)	Вес
a	b	c
0	0	0	0	0	20
0	0	1	1	1	21
0	1	0	3	1	22
0	1	1	3	1	23
1	0	0	4	0	24
1	0	1	5	1	25
1	1	0	6	0	26
1	1	1	7	1	27

Получим восьмеричный код ПФ: 256₈.

Получим шестнадцатеричный код ПФ: AE₁₆.

Получили символическую формулу: f(abc)₁₀ = 1, 2, 3, 5, 7[0, 4, 6].

В двоичном виде: f(abc)₂ = 001₂011₂101₂11₂010₂.

Определим свойства ПФ № 174₁₀.

1.     Поскольку на наборе 000 ПФ равна 0, то ПФ обладает свойством сохранения константы «0».

2.     Поскольку на наборе 111 ПФ равна 1, то ПФ обладает свойством сохранения константы «1».

3.     Рассмотрим все возможные линейные ПФ от трех аргументов в зависимости от значений коэффициентов полинома k₀k₁ck₂bk₃a (табл. 3.18).

Проверим, не равна ли наша функция функциям ab, ac, bc, abc и их инверсиям: , , , .

Следовательно, функция № 174₁₀ – нелинейная.

4.      Определим, обладает ли наша ПФ свойствами самодвойственности.

Для этого проанализируем ее вектор в двоичном коде.

Видим, что симметричные разряды 5 и 2 неортогональны. Следовательно, ПФ – несамодвойственна. У самодвойственной ПФ симметричные разряды ортогональны (противоположны).

5.      Определим, монотонна ли наша ПФ.

Посмотрим на куб соседних чисел. Монотонная функция по всем возможным путям из вершины (000) в вершину (111) монотонна. Однако наша функция на наборе (010) принимает значение «1», а на большем сравнимом наборе (110) – «0». Следовательно, она не монотонная.

                                                                                                       Таблица 5

Переключательные функции от трех аргументов

Значение коэффициентов				Линейная функция
k0	k1	k2	k3
0	0	0	0	0
0	0	0	1	a
0	0	1	0	b
0	0	1	1	ab
0	1	0	0	с
0	1	0	1	ca
0	1	1	0	cb
0	1	1	1	cba
1	0	0	0	1
1	0	0	1	= a1
1	0	1	0	b1=
1	0	1	1	ab1=
1	1	0	0	1c=
1	1	0	1	ca1=
1	1	1	0	1bc=
1	1	1	1	cba1=

Практическая работа № 6, 7

Тема: «Важнейшие замкнутые классы». Функционально-полные системы

Теоретическая часть:

1.    Какие булевы функции, принадлежат классу, сохраняющему 0, сохраняющему 1?

2.    Какие булевы функции, принадлежат классу линейных функций?

3.    Запишите многочлен Жегалкина.

4.    Какая функция называется двойственной для данной?

5.    Какие булевы функции, принадлежат классу самодвойственных функций?

6.    Какие булевы функции, принадлежат классу монотонных функций?

7.    Сформулируйте теорему Поста.

8.    Что такое базис для булевых функций?

Практическая часть:

1) Проверить с помощью теоремы Поста полноту систем булевых функций

                       а) ;              б)

2) Предоставить многочленом Жегалкина функцию 

3) Образует ли система базис?  

4) Определить двойственность функции 

Практическая работа 8

Тема: «Решение задач по теме «Логические рассуждения».

Теоретическая часть:

1.Сформулируйте  Правило modus ponens, или "правило отсечения"
2. Сформулируйте Правило "условного рассуждения"
3. Сформулируйте Правило рассуждения "от противного"

4.Сформулируйте теорему о полноте исчисления высказываний.

5. Сформулируйте правила категоричного силлогизма.

Практическая часть:

1. Проверить правильность непосредственного умозаключения:
«Верблюд – корабль пустыни, значит, среди кораблей пустыни попадаются и не верблюды».
2. Проверить правильность силлогизма: «Так как он не знает правил логики, то он не сможет определить, где в этом рассуждении находится ошибка».
3. Проверить правильность доказательства:
Сын говорит отцу: «Когда я вырасту, то женюсь на бабушке».

Отец:
«Так значит, ты женишься на моей матери?».

 Сын: «Но ты ведь женился на моей матери?».

4.Проверить правильность индуктивного умозаключения:

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

Раздел 6. Предикаты. Исчисление предикатов

Тема 6.1. Предикаты

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

Например,   Х+1>0  зависит от Х. При  Х = 0  оно истинно, а  при  Х = -2 ложно.

Предложения (предикаты), зависящие от переменных, будем обозначать Х(n), У(х), Z(х, у) и т.д. Предложения  Р(х), , не является высказыванием, если оно рассматривается на всем множестве U. Но если Р(х) рассматривать при некотором конкретном значении х = а, то утверждение Р(а) будет либо истинным, либо ложным, т.е. будет высказыванием. Множества U, на котором задано предложение Р(х), можно разбить на два множества. Одно подмножество содержит те элементы U, для которых Р(х) истинно. Оно называется множеством истинности предложения Р(х). Другое подмножество состоит из тех элементов U, для которых Р(х) ложно. Если первое из них обозначим через , то второе множество будет  и тогда получим . Для предложений, зависящих от переменной, так же, как и для высказываний, можно ввести логические операции.

Например,  Отрицанием предложения  называется предложение, определенное на том же множестве U и обращающееся в истинное высказывание для тех и только тех значений Х, для которых Р(х) ложно, обозначаются . Аналогично определяются и другие логические операции.

Знаки общности и существования

С предложениями, зависящими от переменных, связаны два вида часто встречающихся утверждения:

1)   Предложение Р(х), хÎU обращается в истинное высказывание хотя бы для одного элемента множества U. Тогда пишут кратко: (х) Р(х) – существует точное значение хÎU, что Р(х) истинно.

 - знак существования (перевернутая буква английского слова Exists – существует)

2)  Предложение Р(х), хÎU обращается в истинное для всех элементов множества U.

Тогда пишут кратно:  (Р(х) истинно для всех хÎU).

 - знак общности (перевернутая первая буква английского слова All – все).

Примеры:

1)   Даны два высказывания:

       Х: «Петров учится в торговом институте»,

       Y: 7 ≤ 5.

Определить,   какие   из   следующих   высказываний:    а)   ,    б)   ,  в)  → ,  г)  →   истинны, если известно, что  – истинное высказывание.

Решение:

а)    – истинно, т.к.  - истинно;

б)    – ложно, т.к.  - ложно;

в)  →  – истинно, т.к.  - ложно;

г)  →  – ложно, т.к  - истинна,  - ложно.

2)  Истинно или ложно высказывание ()  ( ( )), если Y и Х –  ложные, а Z – истинное высказывание.

Решение:

 =  – истинно, т.к.  Х – ложно    –  истинно, т.к.   – ложно.

Значит,  ( ) – истинно,  значит,  ()  ( ( )) – истинна.

3)  Какие из следующих высказываний равносильны

     а) ,   б) ,   в) ,   г) ,   д)  ?

Решение:   = ,   =  = .

Ответ:  а)  и  б)  равносильны;

5) Студентам объявили: «в понедельник буде одна пара бухучёт и одна математика, причём, если на первой паре математики не будет, то бухучёт будет на второй паре, если третья пара не математика, то четвёртая пара бухучёт, а если математика будет на первой паре, то бухучёт на пятой паре». Определить, на какой паре будет  бухучёт и на какой математика?

Решение:

Пусть х₁ – математика будет на I паре;

          х₃ – математика будет на III паре;

          y₂ – бухучёт будет на II паре;

          y₄ – бухучёт будет на IV паре;

          y₅ – бухучёт будет на V паре.

S = ()  () () = (()  ()) () = (()  () ()()) () = (() ()) () = () () () () =

Ответ:  бухучёт на II паре,  математика на III паре.

6) На множестве всех действительных чисел даны два предложения                                                                                                          (предиката):

       У(х):   «уравнение (относительно t)   »,

       Z(х):   = .

     Найти множество истинности для предложений:

     а) У(х),  б) Z(x),  в) У(х)  Z(x),  г) У(х)  Z(x).

Решение:

а) Уравнение    равносильно  уравнению  .  При   уравнение имеет решение. Значит, множеством истинности У(х) является множество  У = (-∞; -2]  [2; +∞).

б) =

       || ‌‌‌‌‌‌=

       .      .     z = (-∞; 3].

в) У(х)  Z(х):

     У(х)  Z(х) = R

г) У(х)  Z(x) = (-∞; -2]  [2; 3).

Практическая работа №9

Тема: «Непротиворечивость и полнота исчисления предикатов»

Теоретическая часть:

1.    Что понимается под предикатом, его областью определения и множеством истинности? Определить тождественно истинный (ложный) предикат.

2.    Что понимается под квантором общности и существования? Определите операции навешивания этих кванторов на одноместный предикат.

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

4.    Что понимается под предикатной формулой?

Практическая часть:

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

Х делиться на 2 и на У

2) Даны предикаты , , составить предикат

3) При каких значениях  истинно предложение: -«существует , при котором система имеет хотя бы одно решение»?

4) Найти множество истинности предиката ,где , ,

5) На множестве чисел задан двухместный предикат p(x,y)=”число х делиться на у” связывая одну переменную получить одноместные предикаты.

Раздел 7. Элементы теории автоматов.

Тема 7.1. Базовые множества для автоматов.

Алгебра высказываний применяется при анализе рэлейноламповых схем. Под переключательной схемой мы будем понимать схематическое изображения, какого либо устройства, содержащего только двухзначные переключатели, т.е. переключатели, которые могут находиться в двух состояниях: в замкнутом (ток проходит) и разомкнутом (ток не проходит). Связь между переключательными схемами и алгеброй высказываний устанавливается следующим образом. Каждому переключателю ставится в соответствии высказывания, истинное тогда, когда переключатель замкнут, и ложное, если переключатель разомкнут. На схемах переключатели будем обозначать теми же буквами, что и соответствующие им высказывания.

                                 

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

Пример 1:

( Х ^ У) Ú (Х ^ Z) = X ^ (Y Ú Z);

X ^ (YÚ Z).

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

Пример 2:   Упростить схему

( Х ^ Y) Ú ((X Ú Z) ^ ) = (X ^ Y) Ú (X ^ ) Ú (Z ^ ) =

                                         = X ^ (Y Ú ) Ú (Z ^ ) = X Ú (Z ^ ).

Тогда схема имеет вид

Вторая схема оптимальна, т.к. меньше переключателей.

Практическая работа. №10.

Тема: « Решение задач по теории автоматов.»

Теоретическая часть:

1. Понятие об информации и ее преобразованиях. Преобразование алфавитной информации.
2. Основные понятия теории формальных грамматик.
3. Способы задания автоматов.

Практическая часть:

2.1. Для схемы автомата запишите булеву функцию

2.2 Данный автомат представьте табличным способом

Дидактические игры

1.    Учим символы и обозначения

https://learningapps.org/view5169380

2.    Основные тождества алгебры множеств

https://learningapps.org/view5169802

3.    Азы дискретной математики

https://learningapps.org/view5124408

4.    Основы математической логики

https://learningapps.org/view5171748

5.    Предикаты и кванторы

https://learningapps.org/view5172863

6.    Теория графов

https://learningapps.org/view5173415

Основные источники:

1.    Ашинянц Р. А. Логические методы в искусственном интеллекте. – М.: МГАПИ, 2001. – 223 с.

2.    Г.А. Гончарова, А.А. Мочалин  Элементы дискретной математики: Учебник. – М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2007. – 180 с.

3.    Карпов Ю.Г. Теория автоматов – СПб.: Питер,2003.– 208с.,ил.

4.    Курант Р., Роббинс Г. Что такое математика? – Ижевск, НИЦ “Регулярная и хаотическая динамика”, 2015. – 568 с.

5.    Лыскова В. Ю., Ракитина Е. А. Логика в информатике. – М.: Лаборатория Базовых Знаний, 2006. – 160 с.

6.    Спирина М.С., Спирин П.А. Дискретная математика ( М.: НЦ « Академия». 2017, 288с.

7.    Новиков Ф. А. Дискретная математика для программистов. СПб.: Питер, 2009. – 304 с.

8.    Судоплатов С. В. Дискретная математика: учебник и практикум для среднего профессионального образования / С. В. Судоплатов, Е. В. Овчинникова . – 5-е изд., испр. и доп. – Москва : Юрайт, 2020. – 279 с. – (Профессиональное образование). – ISBN 978-5-534-11632-8

9.    Щербина И.А. Дискретная математика- Ростов-на –Дону, «Феникс», 2020-128 с.

Интернет-ресурсы:

http://alice.stup.ac.ru/~dvn/logica/1.htm

http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=231

 http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=112.

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

Методические указания к выполнению практических работ

по дисциплине ЕН.02 «Элементы математической логики»

по специальности 09.02.03 «Программирование в компьютерных системах»

Елена Александровна Шмакова

Отпечатано с готового оригинал-макета в ООО «БиС»

393773, Тамбовская обл., г. Мичуринск, ш. Липецкое, д. 95А

Подписано в печать 19.06.2017 г. Формат 60х84 1/8,

Бумага офсетная № 1. Усл. печ. л. 2,3. Тираж 100 экз. Ризограф

Заказ №

Краткое описание документа:

Методические указания для проведения практических работ предназначены для контроля и оценки результатов освоения дисциплины ЕН.02 «Элементы математической логики».

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

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

Методические указания разработаны на основании ФГОС СПО по специальности 09.02.03 «Программирование в компьютерных системах»», программы учебной дисциплины ЕН.02 «Элементы математической логики».