9. Кто из абитуриентов A, B, C и D играет, а кто не играет в шахматы, если известно следующее: если A или B играет, то C не играет если B не играет, то играют C и B C – играет. Решить задачу с помощью логических операций. 10.В деле об убийстве имеются двое


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
Страница
1




БОУ СПО ВО Грязовецкий политехнический техникумª












Методические рекомендации

по организации внеаудиторной самостоятельной
работы студентов по учебной дисциплине:


ЕН.  Элементы математической логики





9... Компьютерные сети





Преподаватель: Л. В. Белова




Грязовец

15 г.

Страница
2


Пояснительная записка

Методические рекомендации для организации самостоятельной работы по дисциплине
Элементы математической логикиª предназначены для обучающихся 

курса по 9..
Компьютерные сетиª.

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

В соответствии с учебным планом на самостоятельную работу обучающихся отводится 5
часов.

Само
стоятельная работа обучающихся проводится с целью:



систематизации и закрепления полученных теоретических знаний и практических
умений обучающихся;



углубления и расширения теоретических знаний;



развития познавательных способностей и активности обучающихся:
самостоятельности ответственности и организованности творческой инициативы;



формирования самостоятельности мышления способности к саморазвитию
самосовершенствованию и самореализации;



развития исследовательских навыков.

Критериями оценки результатов сам
остоятельной работы обучающихся являются:



уровень усвоения обучающимся учебного материала;



умение обучающегося использовать теоретические знания при выполнении
практических задач;



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



обоснованность и
четкость изложения материала;



уровень оформления работы.

При изучении дисциплины Элементы математической логикиª используются виды
самостоятельной работы направленной на:

формирование умений:



решение логических задач и упражнений по образцу;



составление
таблиц истинности;



использование аудио
-

и видеозаписей компьютерной техники и Интернета;

овладение знаниями:



работа с текстами (учебника первоисточника дополнительной литературы);



составление плана текста;



конспектирование текста;



выписки из текста;

Страница
3




раб
ота со словарями и справочниками;



учебно
-
исследовательская работа;



использование аудио
-

и видеозаписей компьютерной техники и Интернета;


закрепление и систематизацию знаний
:



работа с конспектом лекций учебным материалом (учебником


первоисточником
дополнительной литературой аудио
-

и видеозаписями) в т.ч. по составлению таблиц
для систематизации учебного материала; составлению плана и тезисов ответа; ответов
на контрольные вопросы;



подготовка сообщений к выступлению на уроке;



подготовка рефератов д
окладов;



составление библиографии тематических кроссвордов.




СОДЕРЖАНИЕ


Введение

4

Раздел 1 Множества

5

Раздел  Формулы логики

8

Тема .1 Высказывания

8

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

13

Тема . Применение логических формул

18

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

33

Тема .1 Функции алгебры логики

33

Тема . Многочлен Жегалкина

38

Тема . Булевы уравнения и их системы

43

Раздел  Предикаты

52

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

52

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

55

Тема 5. Машина Тьюринга

55

Внеаудиторная самостоятельная работа

59


Страница
4


Введение


Назначение рабочей тетради


организовать аудиторную и внеаудиторную
самостоятельную работу обучающихся.

В структуру пособия входят следующие разделы:

Раздел 1 Множества


Разде
л  Формулы логики


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

Раздел  Предикаты

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

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


Страница
5


Раздел 1
Множества


Множество



это любая определё
нная совокупность объектов.

Класс


это множество элементами которого являются множества.

Пример. Примеры множеств:

Множество
S

страниц в книге;
Множество
R

вещественных чисел.

Способы задания множеств:



перечисление элементов:
M
k
={
a
1
,
a
2
 …
a
k
}



характеристический предикат:
M
={
x
|
P
(
x
)}



порождающая процедура:
M
={
x
|
x
:=
f
}

Пример. М
9
={1, 2, 3, 4, 5, 6, 7, 8, 9}


перечисление элементов.

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



объединение:
;



пересечение:
;



разность:
;



симметрическая разность:
.

Пример. Произвести над данными множествами все возможные операции.
А
3
1   и
B
3
={3, 4, 5}.





.

Задание
. Совершить над множествами следующие операции: объединение
пересечение разность симметричная разность.

a)

А
7
={1,8,2,9,d,f,c} B
4
={c,4,8,d}







.

b)

А
7
={
e
,
w
,
x
,
t
,
g
,
yy
,
xz
}
B
4
={
x
,
y
,
z
,
t
}







.

c)

А
7
={3
,
41
,
5
,
8
,
9
,
10
,
2} B
4
={1
,
2
,
3
,
4}







.

d)

А
7
={3,4k,2a,5l,3w,1r,2} B
4
={2a,7e,3,1r}







.

Страница
6


e)

А
5
={
gg
,
h
,
t
,
e
,
w
}
B
5
={
p
,
t
,
uu
,
n
,
e
}







.

f)

А
5
={5
,
9
,
7
,
2
,
0} B
5
={4
,
0
,
77
,
5
,
8}







.

g)

А
5
={
v
,
b
,
n
,
m
,
l
}
B
5
={
h
,
j
,
m
,
bn
,
i
}







.

h)

А
5
={0
f
,
h
,1
y
,
q
,5
r
}
B
5
={1
y
,0
g
,
h
,
t
,6}







.

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



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

Пример. Найти все подмножества данного множества. 
x
,
y
,
z
}.

_________________________________________________________________
_____________________________________________________________________
_________________________
____________________________________________
___________

Задание.

Для каждого множества В из задан
ия 1 найти все подмножества
.

a)

B
4
={c,4,8,d}

_________________________________________________________________
_____________________________________________________________________
_______________
______________________________________________________

b)

B
4
={
x
,
y
,
z
,
t
}

_________________________________________________________________
_____________________________________________________________________
________________
____________________________________________________

c)

B
4
={1
,
2
,
3
,
4}

____________________________________
_____________________________
_____________________________________________________________________
________________
_____________________________________________________

Страница
7


d)

B
4
={2a,7e,3,1r}

_________________________________________________________________
_____________________________________________________________________
_______________
______________________________________________________

e)

B
5
={
p
,
t
,
uu
,
n
,
e
}

____________________________________
_____________________________
_____________________________________________________________________
_____________________
________________________________________________

f)

B
5
={4
,
0
,
77
,
5
,
8}

_________________________________________________________________
_______
______________________________________________________________
__________
___________________________________________________________

g)

B
5
={
h
,
j
,
m
,
bn
,
i
}

_________________________________________________________________
_____________________________________________________________________
__________
___________________________________________________________

h)

B
5
={1
y
,0
g
,
h
,
t
,6}

___________________________________
______________________________
_____________________________________________________________________
__________
___________________________________________________________





Страница
8


Раздел
2

Формулы логики


Тема
2
.1
Высказывания


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


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

Таблицы истинности основных логических функций:


НЕ

а


0

1

1

0


И

a

b


0

0

0

0

1

0

1

0

0

1

1

1


ИЛИ

a

b


0

0

0

0

1

1

1

0

1

1

1

1


Эквивалентность

a

b


0

0

1

0

1

0

1

0

0

1

1

1


Импликация

a

b


0

0

1

0

1

1

1

0

0

1

1

1



Пример. Построить таблицу истинности следующей функции
.

Расставляем последовательность действий:
.

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


5 ст
олбцов


11.

Заполняем полученную таблицу следующим образом.

х

у

1

2

3

4

5

6

7

8

9

0

0










0

1










1

0










1

1











Страница
9


Задание.

Постройте таблицы истинности для следующих функций.

1.

х

у










































































2.

a

b

c





































































































































3.

a

b

c





































































































































4.


a

b

c





































































































































5.

x

y











































































Страница
10


6.

P

Q

R

S




























































































































































































































































7.

x

y










































































8.

a

b

c





































































































































9.

P

Q

R

S

















































































































































































P

Q

R

S












Страница
11













































































10.

x

y










































































11.

a

b

c





































































































































11.

P

Q

R

S




























































































































































































































































12.

x

y










































































13.

Страница
12


a

b

c





































































































































14.

P

Q

R

S




























































































































































































































































15.

x

y

z





































































































































16.

x

y











































































Страница
13


17.

x

y

z





































































































































18.

x

y

z






































































































































19.

x

y










































































20.

x

y











































































Тема
2.2

Законы логики


Формулы и законы с помощью которых возможно упрощение сложных
высказываний:

1. Свойства которые исходят из определений дизъюнкции конъюнкции и
отрицания:



. Переместительный закон (закон коммутативности) для логического сложения
и умножения:

Страница
14



. Сочетательный закон (закон ассоциативности) для логического сложения и
умножения:


. Распределите
льный закон (закон дистрибутивности) для логического
умножения по отношению к сложению:



5. Для многих алгебраических преобразований полезными являются тождества
относящиеся к двум и трём переменных:

а)

б)

в)

г)


д)

. К основным законам алгебры логики относятся законы инверсии для
логического сложения и умножения (теоремы де Моргана):


. Закон двойного отрицания
.

8.
Импликацию можно представить в виде
 э
квивалентность


.

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




Задание.

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

1.









Страница
15


2.









3.









4.







5.









6.









7.


Страница
1
6









8.








9.









10.









11.









12.



Страница
17








13.








14.









15.









16.









17.




Страница
18







18.








19.









20.










Тема . Применение логических формул


1.

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

Алгоритм построения:








Страница
19


Пример.

Для функции

построить СКНФ.

1.

Составление таблицы истинности для этого расставим действия:


2.

Построение таблицы истинности

х

у

1

2

3

4

5

6

7

8

9

10

11





















































3.

Составление
СКНФ
: ________________________________

Задание.

Для данных функций построить совершенную конъюнктивную
нормальную форму:

1.

х

у

























































































Составление
СКНФ
: ________________________________

2.


х

у

























































































Составление
СКНФ
: ________________________________

3.


х

у





















































х

у





















































Страница
20


Составление
СКНФ
: ________________________________

4.


a

b

c
































































































































































Составление
СКНФ
: ________________________________

5.


a

b

c
































































































































































Составление
СКНФ
: ________________________________


2.

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

Алгоритм построения:








Пример.

Для функции

построить СДНФ.

1.

Составление таблицы истинности для этого расставим действия:

Страница
21



2.

Построение таблицы истинности

х

у

1

2

3

4

5

6

7

8

9

10

11





















































3.

Составление
С
Д
НФ
: ________________________________

Задание.

Для данных функций построить совершенную
дизъюнктивную
нормальную форму:

1.

х

у

























































































Составление
С
Д
НФ
: ________________________________

2.


х

у

























































































Составление
С
Д
НФ
: ________________________________

3.


х

у

























































































Составление
С
Д
НФ
: ________________________________

4.


a

b

c
















Страница
22


















































































































































Составление
С
Д
НФ
: ________________________________

5.


a

b

c
































































































































































Составление
С
Д
НФ
: ________________________________

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

Как решать логические задачи?

Разнообразие логических задач очень велико.
Способов их решения тоже немало. Но наибольшее распространение получили
следующие три способа решения логических задач:



средствами алгебры логики;



табличный;



с помощью рассуждений.

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

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










Страница
23



Пример.

Трое друзей болельщиков автогонок "Формула
-
1" спорили о результатах
предстоящего этапа гонок.



Вот увидишь Шумахер не придет первым


сказал Джон. Первым будет
Хилл.



Да нет же победителем будет как всегда Шумахер


воскликнул Ник.


А об Алези и говорить нечего ему не быть первым.

Питер к которому обратился Ник возмутился:



Хиллу не видать первого места а вот Алези пилотирует самую мощную
машину.

По за
вершении этапа гонок оказалось что каждое из двух предположений
двоих друзей подтвердилось а оба предположения третьего из друзей оказались
неверны. Кто выиграл этап гонки?

Решение.

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

Ш


победит Шумахер;

Х


победит Хилл;

А


победит Алези.

Реплика Ника "Алези пилотирует самую мощную машину" не содержит
никакого утверждения о месте которое займёт этот гонщик поэтому в дальнейших
рассуждениях не учитывается.

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



Учит
ывая то что предположения двух друзей подтвердились а предположения
третьего неверны запишем и упростим истинное высказывание











Высказывание истинно только при
_____________________________________

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

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

Пример.

Страница
24


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

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

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

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

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

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

5. Браун не умеет играть ни на трубе ни на гобое.

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

Решение.

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


скрипка

флейта

альт

кларнет

гобой

труба

Браун







Смит







Вессон


























Ответ:



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

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

Пример.

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


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

Решение.

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

1. Вадим изучает китайский;

. Сергей не из
учает китайский;

. Михаил не изучает арабский.



















Ответ.


Задание.

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

1.

Три дочери писательницы Дорис Кей


Джуди Айрис и Линда тоже очень
талантливы. Они приобрели известность в разных видах
искусств


пении балете и
кино. Все они живут в разных городах поэтому Дорис часто звонит им в Париж
Рим и Чикаго.

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

-

Джуди живет не в Париже а Линда


не в Риме;

-

парижанка не снимается в кино;

-

та кто живет в Риме певица;

-

Линда ра
внодушна к балету.

Где живет Айрис и какова ее профессия?





Страница
26


















2.

Пытаясь вспомнить победителей прошлогоднего турнира пять бывших
зрителей турнира заявили:

-

Антон был вторым а Борис
-

пятым.

-

Виктор был вторым а Денис
-

третьим.

-

Григорий был первый а Борис
-

третьим.

-

Антон был третьим а Евгений
-

шестым.

-

Виктор был третьим а Евгений
-

четвертым.

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

















Страница
27






3.

В школе перешедшей на самообслуживание четырем старшеклассникам:
Андрееву Костину Савельеву и Давыдову поручили убрать 
-
ой 
-
ой 9
-
ый и 1
-
ый классы. При проверке оказалось что 1
-
ый класс убран плохо. Не ушедшие
домой
ученики сообщили о следующем:

-

Андреев: Я убирал 9
-
ый класс а Савельев


7
-
ойª.

-

Костин: Я убирал 9
-
ый класс а Андреев


8
-
ойª.

-

Савельев: Я убирал 
-
ой класс а Костин
-

10
-
ыйª.

Давыдов уже ушел домой. В дальнейшем выяснилось что каждый ученик в
одном из двух высказываний говорил правду а во втором ложь. Какой класс убирал
каждый ученик?





















4.

Пять школьников из пяти различных городов Брянской области прибыли для
участия в областной олимпиаде по математике. На вопрос: Откуда Вы?ª
каждый
дал ответ:

-

Иванов: Я приехал из Клянцов а Дмитриев из Новозыбковаª.

-

Сидоров: Я приехал из Клянцов а Петров из Трубчевскаª.

-

Петров: Я приехал из Клянцов а Дмитриев из Дятьковаª.

-

Дмитриев:  Я приехал из Новозыбкова а Ефимов из Жуковки
ª.

-

Ефимов:  Я приехал из Жуковки а Иванов из живет в Дятьковеª.

Страница
28


Откуда приехал каждый из школьников если одно его утверждение верно а
другое ложно?





















5.

На соревнованиях по легкой атлетике Андрей Борис Сергей и Володя
заняли первые

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

-

Даша сказала: "Андрей был первым а Володя
-

вторым".

-

Галя утверждала: "Андрей был вторым а Борис
-

третьим".

-

Лена считала: "Бор
ис был четвертым а Сергей
-

вторым".

Ася которая была судьей на этих соревнованиях и хорошо помнила как
распределились места сказала что каждая из девочек сделала одно правильное и
одно неправильное заявление. Кто из мальчиков какое место занял?












Страница
29











6.

Кто из друзей (Иван Петр Алексей Николай или Борис) коллекционирует
марки если известно что:

-

если Борис коллекционирует марки то их коллекционируют Иван и Николай;

-

если их коллекционирует Иван то Петр тоже коллекционирует марки;

-

из двух друзей (Петра и Алексея) коллекционирует марки только один;

-

Алексей лишь в том случае коллекционирует марки если их коллекционирует
Николай;

-

по крайней мере Николай или Борис коллекционирует марки.





















7.

На вопрос кто из
трех абитуриентов A B C может работать на компьютере
был получен ответ: если может работать B то может работать и C но не верно что
если может работать A то может работать и C. Кто из трех абитуриентов может
работать на персональном компьютере?


Страница
30





















8.

На олимпиаде по информатике студенты A B C и  заняли первые четыре
места. Когда их спросили о распределении мест они дали три ответа: 


первый
или B


второй; C


первый или A


четвертый; 


второй или B


третий. Как
распределились

места если в каждом ответе только одно утверждение истинно?



















Страница
31




9.

Кто из абитуриентов A B C и  играет а кто не играет в шахматы если
известно следующее: если A или B играет то C не играет; если B не играет то
играют C и B; C


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





















10.

В деле об убийстве имеются двое подозреваемых: A и B. Допросили
четверых свидетелей. Показания первого таковы: A не виноватª. Второй свидетель
сказал: B не виноватª. Третий
свидетель: Из двух показаний по крайней мере
одно истинноª. Четвертый: Показания третьего свидетеля ложныª. Четвертый
свидетель оказался прав. Кто же совершил преступление?













Страница
32











Страница
33


Раздел
3

Булевы функции


Тема
3
.1
Функции алгебры логики


Булевы функции



это функции типа
.

Булевы функции одной переменной:

x





1







0

0

0

1

1

1

0

1

0

1

Функции








константы  и 1 т.е. функции с двумя несуществующими
переменными.

Функция

1



равна х
1
. Функция





равна
.

Булевы функции двух переменных:

x
1

x
2





1











5











9


1


11


1


1


1


15

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

1

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

Функции




15



константы  и 1 т.е. функции с двумя несуществующими
переменными.

Функция

1



конъюнкция (логическое умножение).

Функция





дизъюнкция (логическое сложение).

Функция





функция сложения по модулю . Обозначается
.

Функция

9



эквивалентность. Функция

1



импликация.

Функция





стрелка Пирса. Обозначается
.

Функция

1



штрих Шеффера. Обозначается
.

Функция





равна х
1
. Функция

1



равна
.

Функция

5



равна х
2
. Функция

1



равна
.

Пример. Какую функцию реализует формула:

х

у














0

0














0

1














1

0














1

1














Данная
формула реализует функцию: _______________________

Страница
34


Задание.

Какую функцию реализует формула.

1.


х
1

х
2














0

0














0

1














1

0














1

1














Данная формула реализует функцию:
_______________________

2.


х
1

х
2














0

0














0

1














1

0














1

1














Данная формула реализует функцию: _______________________

3.


х
1

х
2














0

0














0

1














1

0














1

1














Данная формула реализует функцию: _______________________

4.


х
1

х
2














0

0














0

1














1

0














1

1














Данная формула реализует
функцию: _______________________

5.


х
1

х
2














0

0














0

1














1

0














1

1














Данная формула реализует функцию: _______________________

Страница
35


6.


х

у














0

0














0

1














1

0














1

1














Данная формула реализует функцию: _______________________

7.


х

у














0

0














0

1














1

0














1

1














Данная формула
реализует функцию: _______________________

8.


х
1

х
2














0

0














0

1














1

0














1

1














Данная формула реализует функцию: _______________________

9.


х
1

х
2














0

0














0

1














1

0














1

1














Данная формула реализует функцию: _______________________

10.


х
1

х
2














0

0














0

1














1

0














1

1














Данная
формула реализует функцию: _______________________

Страница
36


11.


х
1

х
2














0

0














0

1














1

0














1

1














Данная формула реализует функцию: _______________________

12.


х
1

х
2














0

0














0

1














1

0














1

1














Данная формула реализует функцию: _______________________

13.


х

у














0

0














0

1














1

0














1

1














Данная формула реализует функцию: _______________________

14.


х

у














0

0














0

1














1

0














1

1














Данная формула реализует функцию: _______________________

15.


х
1

х
2














0

0














0

1














1

0














1

1














Данная формула реализует функцию: _______________________

16.


х
1

х
2














0

0














0

1














1

0














1

1














Данная формула реализует функцию: _______________________

Страница
37


17.


х
1

х
2














0

0














0

1














1

0














1

1














Данная формула реализует функцию: _______________________

18.


х
1

х
2














0

0














0

1














1

0














1

1














Данная формула реализует функцию: _______________________

19.



х
1

х
2














0

0














0

1














1

0














1

1














Данная формула реализует функцию: _______________________

20.



х

у














0

0














0

1














1

0














1

1














Данная формула реализует функцию: _______________________

21.


х

у














0

0














0

1














1

0














1

1














Данная формула реализует функцию: _______________________


Страница
38


Тема
3.2

Многочлен Жегалкина


Иван Иванович Жегалкин

( июля (
 августа
)
1869
,
Мценск
,
Российская империя



28

марта

1947
,
Москва
,
СССР
)



российский

и
советский

математик и логик. Из его открытий
наибольшую известность получил так называемый
полином Жегалкина
.

И.

И.

Жегалкин в
19 году
 окончив
Орловскую гимназию
 стал студентом математического
отделения
физико
-
математического факультета Московского университета
. В
19 году

он
окончил университет с дипломом 1
-
й степени и начал службу сразу в нескольких учреждениях: в
Государственном банке и на вечерних курсах Общества распространения коммерческого
образования. С
19 года

преподавал в
реальном училище К.

К.

Мазинга
. В 19 году выдержав
магистерский экзамен стал приват
-
доцентом университета; защита магистерской диссертации
Трансфинитные чи
слаª состоялась только в 19 году.

В
1911 году

Жегалкин будучи несогласным с политикой проводимой
Л.

А.

Кассо
 бывшим
тогда министром просвещения ушёл с большой группой преподавателей из университета. До
возвращения в университет в
191 году
 Жегалкин преподавал на
Высших женских курсах
. Здесь
он после открытия в
19 году

медицинско
го факультета временно исполнял должность декана
факультета. Будучи членом
Московского математического общества
 заведовал в нём
библиотекой.

После возвращения в университет И.

И.

Жегалкин стал в
19 году

профессором
математики
а в
19 году

назначен заведующим кафедрой математического анализа физико
-
механического факультета преобразованного через  года в
механико
-
математический факультет
.
Одновременно он заведовал кафедрой математики в
Московском областном педагогическом
институте
.

По инициативе И.

И.

Жегалкина была создана группа математической логики ставшая
основой для образования в
1959 году

кафедры математической логики возглавленной
С. А.
Яновской
.

Жегалкин представил алгебру логики как арифметику
вычетов по модулю

. Также ему
принадлежит ряд работ о важных случаях допускающих алгоритмическое р
ешение
проблемы

разрешимости
. Жегалкин награждён Орденом Трудового Красного Знамени. В своём письме
М.

Я.

Выгодскому

известный советский математик
Николай Лузин
 вспоминая студенческие годы
говорит что из профессоров не боялся лишь Жегалкина.

Соотношения выполняющиеся в алгебре Жегалкина:

1.

2.

3.

4.

5.


6.

Пример. Упростить


Задание.

Привести данное логическое выражение к виду алгебры Жегалкина.

1.







Страница
39





2.










3.










4.










5.










6.


Страница
40










7.










8.










9.










10.






Страница
41






11.










12.










13.










14.









15.


Страница
42










16.










17.










18.










19.






Страница
43






20.










Тема . Булевы уравнения

и их системы


Булевы уравнения

Способы решения:

1.

Сведение к одному уравнению:











Пример. Решить уравнение
.

Решение.










2.

Построение таблиц истинности

Страница
44












Пример. Решить уравнение

Решение.

Х

1

2

3

0




1




3.
Декомпозиция










Пример. Решить уравнение


Решение.

Х








Х1





Страница
45





Задание. Решить

уравнения всеми методами






































Страница
46










































Страница
47










































Страница
48













Система булевых уравнений

Способы решения

1.

Построение таблиц истинности













Пример. Решить систему уравнений:


Х

У

1

2

3

4

0

0





0

1





1

0





1

1









2.

Декомпозиция




Страница
49










Пример. Решить систему уравнений:


Решение.

Х








Х1








Задание.

Решить системы уравнений всеми методами.












Страница
50






































Страница
51

































Страница
52


Раздел
 Предикаты


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


Понятие предиката и операции над предикатами.
n
-
Местным предикатом (или
функцией
-
высказыванием от
n

переменных) определенным на множествах
(областях) М
1
 М
2
 ... М
n

называют выражение содержащее
n

(предметных)
переменных х
1
 х
2
 ... х
n
 превращающееся
в высказывание при подстановке вместо
этих переменных конкретных элементов (предметов) из множеств М
1
 М
2
 ... М
n

соответственно. Для
n
-
местного предиката будем использовать обозначение Р(х
1
,
х
2
 ... х
n
). Высказывание будем считать 
-
местным предикатом
.

На предикаты естественным образом переносятся все операции (логические
связки) которые мы проделывали над высказываниями. Например дизъюнкцией
n
-
местных предикатов Р(х
1
 х
2
 ... х
n
) и Q(х
1
 х
2
 ... х
n
) заданных над множествами М
1
,
М
2
 ... М
n

наз
ывают новый
n
-
местный предикат над этими множествами
обозначаемый Р(х
1
 х
2
 ... х
n
) v Q(х
1
 х
2
 ... х
n
) который обращается в ложное
высказывание на тех и только тех значениях переменных из множеств М
1
 М
2
, ...,
М
n
 на которых в ложное высказывание обращаются оба данных предиката.

Задание.

Для каждого из
следующих высказываний найдите
предикат
(одноместный или многоместный) который обращается в данное высказывание при
замене предметных переменных

подходящими значе
ниями из соответствующих
областей:

а)     ª;

б) Вера и Надежда


сестрыª;

в) Сегодня


вторникª;

г) Город Саратов находится на берегу реки Волгиª;

д) 
sin

°  5ª;

е) А. С. Пушкин


великий русский поэтª;

ж) З    5ª;

з) Река Ин
дигирка впадает в озеро Байкалª;

163

и) Если число делится на  то оно делится на 9ª;

к) Луна есть спутник Марсаª;

л) 
tg
(

/4) =
l
ª.

Построив такой предикат постарайтесь или точно указать его область
истинности или как
-
то ее обрисовать.

Решение.

л)
Можно указать три предиката каждый из которых обращается в
данное высказывание при соответствующей подстановке. Первый предикат
одноместный: 
tgx

 1ª (
). Он превращается в данное
высказывание при подстановке х 

/. Получающееся высказывание истинно.
Указанным значением не исчерпывается множество истинности построенного
предиката. Как нетрудно установить это множество следующее:
.
Второй предикат также одноместный: 
tg
(

/)  уª (
). Он превращается в
данное высказывание при подстановке у  1. Ясно что этим значением и
исчерпывается множество истинности этого предиката. Наконец можно построить
Страница
53


третий предикат двухместный: 
tgx

 уª (
). Он
превращае
тся в данное высказывание при подстановке х 

/ у  1. Его область
истинности представляет собой множество упорядоченных пар совокупность
которых графически изображается в виде бесконечного семейства кривых
называемых тангенсоидами.

а)     ª ___
______________________________________________________

______________________________________________________________________

________________________________________________________________________
__________________________________________________________
______________
________________________________________________________________________
________________________________________________________________________

б) Вера и Надежда


сестрыª _________________________________________

__________________________
____________________________________________

________________________________________________________________________
________________________________________________________________________
___________________________________________________________________
_____
________________________________________________________________________

в) Сегодня



вторникª

______________________________________________

______________________________________________________________________

________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________
________________________________

г) Город Саратов н
аходится на берегу реки Волгиª ______________________

______________________________________________________________________

________________________________________________________________________
_______
_________________________________________________________________
________________________________________________________________________
________________________________________________________________________

д) 
sin

°  5ª __________________________________________________

______________________________________________________________________

________________________________________________________________________
__________________________________________________
______________________
________________________________________________________________________
________________________________________________________________________

е) А. С.
Пушкин


великий русский поэтª _____________________________

__________________
____________________________________________________

________________________________________________________________________
________________________________________________________________________
___________________________________________________________
_____________
________________________________________________________________________

ж) З    5ª ____________________________________________________

______________________________________________________________________

____________________________
____________________________________________
________________________________________________________________________
________________________________________________________________________
____________________________________________________________________
____

Страница
54


з) Река Инд
игирка впадает в озеро Байкалª ______________________________

______________________________________________________________________

________________________________________________________________________
__________________________________
______________________________________
________________________________________________________________________
________________________________________________________________________

и) Если число дели
тся на  то оно делится на 9ª _______________________
_

______________________________________________________________________

________________________________________________________________________
________________________________________________________________________
_______________________________________
_________________________________
________________________________________________________________________

к) 
Луна есть спутник Марсаª _________________________________________

______________________________________________________________________

________
________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________
________________________



Страница
55


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


Тема
5.2

Машина Тьюринга


Машина Тьюринга
-

это очень простое вычислительное устройство. Она
состоит из ленты бесконечной длины разделенной на ячейки и головки которая
перемещается вдоль ленты и способна читать и записывать символы. Также у
машины Тьюринга есть такая характерист
ика как состояние которое может
выражаться целым числом от нуля до некоторой максимальной величины. В
зависимости от состояния машина Тьюринга может выполнить одно из трех
действий: записать символ в ячейку передвинуться на одну ячейку вправо или
влево
и установить внутреннее состояние.

В 19 г. Алан Тьюринг расширил определение описав "универсальную
машину Тьюринга". Позже для решения определенных классов задач была введена
ее разновидность которая позволяла выполнять не одну задачу а несколько.

С
войства машины Тьюринга как алгоритма





















Страница
56


Описание

машины Тьюринга.

Каждая ячейка содержит ровно один из символов  или 1. Лента представляется
конечной но дополняемой в любой момент ячейками слева и справа для записи
новых символов  или

1. Эта ситуация может возникнуть при сдвиге каретки влево
или вправо за край ленты. Тогда наращивается новая клетка с содержимым . Это
соглашение отражает идею о сколь угодно большой но конечной памяти.

Если каретка расположена над некоторой ячейкой с
символом  (с символом
1) то говорим что каретка обозревает символ  (обозревает символ 1)


Программы машины Тьюринга
.












Выполнение инструкции.

Рассмотрим как выполняется инструкция

(i, a, x, y, z)

с номером
i
.

1) Машина смотрит обозреваемый
кареткой

символ. Если он равен  то
исполняется команда
(i, 0,

x, y, z)
,

если обозреваемый символ равен 1 то
исполняется команда
(i,1, x, y, z)
.

Если команды с таким началом нет то машина
останавливается.
Это единственное условие остановки машины Тьюрин
га.

) Запись в обозреваемую ячейку величины
x
.

Поэтому содержимое
обозреваемой ячейки останется прежним или сменится на противоположное
например  заменится на 1.

) Сдвиг каретки на одну ячейку влево при
y=L

или вправо при
y=R
.

) Переход к инструкции
с номером
z
.

Выполнение инструкции с номером
i
 т. е. выполнение пунктов 1)


4)
считается одним тактом работы машины.

Пример работы программы.

Пусть дана машина Тьюринга с программой из одной инструкции
(0, 0, 1, R, 0)
.

Страница
57


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

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

символ .



Решение.














Другие варианты определения машины Тьюринга.

Рассмотрим другие способы определения машины Тьюринга.

Пусть имеется
некоторый алфавит

A={a
0
, a
1
, a
2
, ... , a
n
}
,

который мы будем называть внешним
алфавитом.

Элементами алфавита

A

будем заполнять ячейки ленты при этом
символ
a
0

будет служить для обозначения пустой ячейки.

Пусть имеется другой алфавит

Q={q
0
, q
1
, q
2
, ... , q
m
}
,

который мы будем
называть внутренним
алфавитом.

Этот алфавит мы будем использовать для
обозначения состояний машины
M
 при этом символ
q
1

будет служит для
обозначения начального состояния символ
q
0



для обозначения заключительного
состояния.

Команды из которых составляются программы имеют

один из трех видов:

Страница
58


1)
q
i
a
j

q
k
a
l
, 2)
q
i
a
j

q
k
a
l

L
, 3)
q
i
a
j

q
k
a
l

R
,

где
1
i
m
,
0
j
n
.

Легко видеть что число различных команд равно
m(n+1)
.

Команда с началом
q
i
a
j

срабатывает

если машина
M

находится в состоянии

q
i

и каретка обозревает
символ
a
j
.

Поэтому
в программе должна быть ровно одна

команда с началом
q
i
a
j
.

Действия при исполнении данных команд следующие:











Пример
.
Задаётся машина Тьюринга внешним алфавитом

A

= {
a
,
b
,
c
 алфавитом внутренних состояний
Q

= {
q
0
,
q
1
,
q
2
,
q
3
 и программой:

1.

q
1
a


q
1
Л
a,

2.

q
2
a


q
3
П
b,

3.

q
3
a


q
1
Л
a,

4.

q
1
b


q
2
Л
a,

5.

q
2
b


q
2
Л
b,

6.

q
3
b


q
3
П
b,

7.

q
1
c


q
0
a,

8.

q
2
c


q
2
Л
c,

9.

q
3
c


q
3
П
c,

10.

q
2




q
2
Л
a.


Применим программу к слову
bbcbb
. Каретка находится в крайней
правой
позиции.

Запишем программу в виде таблицы:


q
1

q
2

q
3

a

q
1
Л
a

q
3
П
b

q
1
Л
a

b

q
2
Л
a

q
2
Л
b

q
3
П
b

c

q
0
a

q
2
Л
c

q
3
П
c

Решение
.

bbcbq
1
b









Страница
59


Внеаудиторная самостоятельная работа

Задание 1.

Записать законы упрощения множеств.



















Вопросы для
самоконтроля.

I.

Множества


это _______________________________________________

____________________________________________________________________

II.

Перечислите операции которые можно совершать над множествами ___

___________________________________________
________________________


Задание
2
.

Упросить предложенные множества используя законы
упрощения.

на удовлетворительно

_____________________________________________________________________
______________________________________________
_______________________
_____________________________________________________________________
_____________________________________________________________________
__________________
_________________________

на хорошо

_____________________________________________________________________
_____________________________________________________________________
_____________________________________________________________________
Страница
60


_________________________________________________
____________________
__________________
___________________

_____________________________________________________________________
_____________________________________________________________________
_____________________________________________________________________
_________________________________________________
____________________
__________________
___________________

на отлично

_____________________________________________________________________
_____________________________________________________________________
___________________________
__________________________________________
_____________________________________________________________________
__________________
___________________________________________________
_______________________________

______________________
_______________________________________________
_____________________________________________________________________
_____________________________________________________________________
_____________________________________________________________________
__
________________
___________________________________________________
______________________________

_____________________________________________________________________
___________________________________________________________________
__
_____________________________________________________________________
_____________________________________________________________________
__________________
___________________________________________________
_________________________________

Вопросы для с
амоконтроля.

I.

Для чего необходимо производить упрощение множеств? _____________

_____________________________________________________________________
___________________________________________________________________

II.

Перечислите способы описания множеств. _
________________________

_____________________________________________________________________
__________________________________________________________________


Задание
3
.

Составить конспект на тему: Аристотель


основоположник
логикиª.






Страница
61





























Вопросы для самоконтроля.

I.

В чём заключается традиционная формальнаяª логика Аристотеля.

II.

Высказывание


это …


Задание
4
.

Упростить данные высказывания используя законы логики.

на удовлетворительно

_____________________________________________________________________
_____________________________________________________________________
_____________________________________________________________________
_________________________________________________
____________________
__________________
_________________________

на хорошо

_____________________________________________________________________
Страница
62


_____________________________________________________________________
______________________
_______________________________________________
_____________________________________________________________________
_______________
___
___
___________________

_____________________________________________________________________
_____________________________________________________________________
_____________________________________________________________________
_________________________________________________
____________________
__________________
______________________

на отлично

_____________________________________________________________________
_____________________________________________________________________
________________________
_____________________________________________
_____________________________________________________________________
__________________
___________________________________________________
___________________________________

_______________
______________________________________________________
_____________________________________________________________________
_____________________________________________________________________
____________________
____________________________________________
_____
______________________________________

_____________________________________________________________________
_____________________________________________________________________
____________________________________________________
_________________
_____________________________________________________________________
__________________
___________________________________________________
____________________________________

Вопросы для самоконтроля.

I.

Логика


это
___________________________________________________

_____________________________________________________________________
_____________________________________________________________________
__________________________________________________________________
_

II.

Для чего необходимо производить упрощение высказываний? _________

_____________________________________________________________________
_____________________________________________________________________
__________________________________________________
___________________
____________________________________________________________________


Задание 5.
Для данного

высказывания построить СДНФ.

на удовлетворительно

Страница
63



х

у










































































СДНФ: ___________________________________________

на хорошо


х

у










































































СДНФ: ___________________________________________


a

b

c





































































































































СДНФ: ___________________________________________

на отлично


a

b

c





































































































































СДНФ: ___________________________________________


P

Q

R

S












Страница
64









































































































































P

Q

R

S





















































































































СДНФ:
___________________________________________

Вопросы для самоконтроля.

I.

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


это

________________________________________

_____________________________________________________________________
_____________________________________________________________________
_____________________________________________________________________
_________________________________________________
_________________

II.

Опишите алгоритм построения таблиц истинности с помощью
табличного редактора.

_
_________________________________________________

_____________________________________________________________________
________________________________________
_____________________________
_____________________________________________________________________
_____________________________________________________________________
_____________________________________________________________________
____________________
_________________________________________________
_____________________________________________________________________
_____________________________________________________________________


Задание
6
.

Для данного высказывания построить СКНФ.

на удовлетворит
ельно


х

у










































































СКНФ: ___________________________________________

на хорошо

Страница
65



х

у










































































С
К
НФ: ___________________________________________


a

b

c





































































































































СКНФ:
___________________________________________

на отлично


a

b

c





































































































































СКНФ:
___________________________________________


P

Q

R

S

















































































































































































Страница
66













































































СКНФ: ___________________________________________

Страница
67


Вопросы для самоконтроля.

I.

Формула


это__________________________________________________

_____________________________________________________________________
_____________________________________________________________________
__________________________________________________________________

II.

Опишите алгоритм построения таблиц истинности. ____
______________

_____________________________________________________________________
_____________________________________________________________________
_____________________________________________________________________
__________________________________
___________________________________
_____________________________________________________________________
__________________________________________________________________


Задание
7
.

Решить данную логическую задачу.

на удовлетворительно

В одном доме живут
три товарища
-

школьники Боря Вася и Дима.

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

Известно что: 1) Васин друг с огорчением сказал: Вчера я не сумел
реализовать пенальтиª;

) товарищ п
оэта сказал:  Дима! Написал бы ты стих и для нашей
футбольной командыª.

Назовите имена футболиста поэта и шахматиста.










на хорошо

Министры иностранных дел России США и Китая обсудили за закрытыми
дверями проекты соглашения о полном разоружении представленные каждой из
стран. Отвечая затем на вопрос журналистов: "Чей именно проект был принят?"
министры дали такие ответы:

Россия


"Проект не наш проект не США";

США


"Проект не России проект Китая";

Китай


"Проект не наш проект России".

Один из них (самый откровенный) оба раза говорил правду; второй (самый
скрытный) оба раза говорил неправду третий (осторожный) один раз сказал
правду а другой раз


неправду.

Определите представителями каких стран являются откровенный
скрытный и остор
ожный министры.

Страница
68













на отлично

Учитель математики проверив олимпиадные работы учеников сказал что
первые три места заняли Сергей Василий и Алексей

причём Сергей занял не
первое место Василий
-

не второе а Алексей
-

второе место.

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













Вопросы для самоконтроля.

II.

Обосновать выбор способа решения задачи. ________________________

_____________________________________________________________________
_____________________________________________________________________
__________________________________________________________________

III.

Какой способ решения логических задач наиболее унив
ерсален. _______

_____________________________________________________________________
_____________________________________________________________________
_____________________________________________________________________
________________________________
___________________________________


Задание
8
.

Составить конспект на тему Биография Дж. Буляª.



Страница
69

































1.

Вопросы для самоконтроля.

I.

Укажите в чём заключается вклад Дж. Буля в развитие математической
логики.
_______________________________________________________________

_____________________________________________________________________
_____________________________________________________________________
______________________________________________________
_______________
____________________________________________________________________

II.

Перечислите основные труды Дж. Буля в области математической
логики. _______________________________________________________________

_______________________________________
______________________________
_____________________________________________________________________
Страница
70


_____________________________________________________________________
_____________________________________________________________________
___________________
_________________________________________________


Задание 9.
Привести

данные формулы логики к виду алгебры Жегалкина

на удовлетворительно

_____________________________________________________________________
__________________________
___________________________________________
_______________________________________________

на хорошо

_____________________________________________________________________
_____________________________________________________________________
__________________________________________________
___
_
_______________
____________________________________________

на о
тлично

_____________________________________________________________________
_____________________________________________________________________
_____________________________________________________________________
____________________
________________
_________________________________
________________________________________

Вопросы для самоконтроля.

I.

Приведите краткое описание биографии Жегалкина. _________________

_____________________________________________________________________
_____________________________________________________________________
_____________________________________________________________________

II.

Постройте таблицу истинности операции сложения п
о модулю .

x

y


0

0


0

1


1

0


1

1



Задание 1
0
.

Решить данные системы булевых уравнений.

на удовлетворительно







Страница
71


на хорошо









на отлично










Вопросы

для самоконтроля.

I.

Булева функция


это

___________________________________________

_____________________________________________________________________
____________________________________________________________________

II.

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

x





1







0





1






Задание 11.
Определить какие из выражений являются предикатами.

а) х делится на 5ª (
) _________________________

б) Река х впадает в озеро
Байкалª (х пробегает множество
названий
всевозможных рек) _________________________

в) х
2

 х  ª (
)_________________________

г) (х  у)
2

 х
2

 ху  у
2
ª (
)_________________________

д) х есть брат уª (х у п
робегают множество всех людей)

_____________

е) х и у лежат по разные стороны от
z
ª (
x
 у пробегают
множество всех
точек
а

z



всех прямых одной плоскости) _________________________

ж)ctg5° 1ª _________________________

з) х перпендикулярна уª
(х у пробегают множество всех прямых

одной
плоскости) _________________________

Страница
72


и) х
2

 х
-

  ª (
)_________________________

к) Для всех вещественных чисел х выполняется равенство х
2

 х
-

6 = 0
ª
_________________________

Вопросы для самоконтроля.

I.

Высказывание


это

...

II.

Предикат


это …

III.

Описать отличие выражения и предиката.


Задание 1
2
.

Составить конспект на тему Нормальный алгоритм Марковаª.




























Страница
73


1.

Вопросы для самоконтроля.

I.

Выделите основные этапы в биографии А.А. Маркова (младшего).

_
____

_____________________________________________________________________
_____________________________________________________________________
_____________________________________________________________________
_________________________________________________
____________________
_____________________________________________________________________
_____________________________________________________________________
_____________________________________________________________________
_____________________________
________________________________________
_____________________________________________________________________
_____________________________________________________________________
_____________________________________________________________________
_______
__
___
______________________________________________________


Задание 1
3
.

Составить конспект на тему: Обращение функций в логикеª.




























Страница
74























Приложенные файлы

  • pdf 14982979
    Размер файла: 2 MB Загрузок: 0

Добавить комментарий