Лекции мат логика. Курс лекций по элементам математической логике Балашиха 2014 г 1

• Название: Курс лекций по элементам математической логике Балашиха 2014 г 1
• Анкор: Лекции мат логика
• Дата: 15.05.2022
• Размер: 0.79 Mb.
• Имя файла: logika_lekcii_1.pdf
• Тип: Курс лекций; #530181
• страница: 1 из 5

Министерство образования Московской области Государственное бюджетное образовательное учреждение среднего профессионального образования Московской области Балашихинский промышленно-экономический колледж
И.А. КАВЕРИНА Курс лекций по элементам математической логике Балашиха 2014 г

1
Каверина И.А. Курс лекций по элементам математической логике. Учебно- методическое пособие. - Балашиха Балашихинский промышленно- экономический колледж, 2014, 65 с. Пособие разработано в соответствии с требованиями федерального государственного образовательного стандарта по курсу Элементы математической логики. Для студентов среднего профессионального образования по специальности
230115 Программирование в компьютерных системах.
Библиогр. 9 назв. Составитель доцент, к.ф.-м.н. И.А. Каверина

2 Введение Зададимся вопросом для чего программисту нужен данный курс. Краткий ответ Изучение его преследует две цели – изучить логические основы процесса написания программ и приобрести навыки строгого, формализованного мышления. А теперь более подробно. Математика является наукой, в которой все истины доказывают с помощью умозаключений. Поэтому для математики большое значение имеют логические теории как средства построения математических знаний (logos (греч.)–слово, понятие, рассуждение, разум).
Логика – это наука, изучающая методы доказательств и опровержений, то есть методы установления истинности или ложности одних высказываний утверждений) на основе истинности или ложности других. Рассмотрим вкратце этапы развития логики. й этап. Как самостоятельная наука логика оформилась в трудах Аристотеля (в. до н.э.). Он пытался найти ответ на вопрос как мы рассуждаем, изучал правила мышления. Аристотель впервые дал систематическое изложение логики. В результате возникла формальная теория, связана с анализом наших обычных содержательных умозаключений, выражаемых разговорным языком, которая впоследствии стала называться формальной или Аристотелевой логикой. Правила вывода, описанные Аристотелем (силлогизмы, были основным инструментом логики вплоть до в. Силлогизм - это рассуждение, в котором из заданных двух суждений выводится третье. Например
1) Все млекопитающие имеют скелет. Все киты
–
млекопитающие. Следовательно, все киты имеют скелет.
2) Все квадраты ромбы, все ромбы
–
параллелограммы.

3 Следовательно, все квадраты
–
параллелограммы. В общем виде этот силлогизм имеет форму Все A суть B, все B суть C. Следовательно, все A суть C.” А вот пример силлогизма неправильной формы Все квадраты
–
ромбы. Некоторые ромбы имеют острый угол. Следовательно, некоторые квадраты имеют острый угол. Значит, силлогизм, имеющий форму Все A суть B, некоторые B суть C. Значит, некоторые A суть C может привести и к ложным выводам. Аристотель выделил все правильные формы силлогизмов, которые можно составить из рассуждений вида "Все A суть B"; "Некоторые A суть B"; "Все A не суть B"; "Некоторые A не суть B". й этап. Однако, развитие математики выявило недостаточность формальной логики, поэтому в конце в. Г.Лейбниц предложил понятия логики обозначить символами, которые соединялись бы по особым правилам. Это позволяло всякое рассуждение заменить вычислением. Первая реализация идей Г.Лейбница принадлежит английскому математику
Дж.Булю (1815-1864). Он создал алгебру, в которой буквами обозначены высказывания, и это привело к алгебре высказываний (или булевой алгебре. Именно благодаря введению символов в логику была получена основа для создания новой науки – математической логики. Математическая логика – это современная форма логики, которая полностью опирается на формальные математические методы. Применение математики к логике позволило представить логические теории в новой удобной форме и применить вычислительный аппарат к решению задач, малодоступных человеческому мышлению. й этап связан с XX веком и попытками обосновать справедливость математических доказательств, с исследованиями теории чисел, а также с попыткой разрешить известные логические парадоксы.

4 Самым знаменитым следует считать парадокс лжеца, известный еще со времен глубокой древности Некто говорит я лгу. Если он при этом лжет, то сказанное им есть ложь, и, следовательно, он не лжет. Если же он не лжет, то сказанное им есть истина, и следовательно, он лжет. В любом случае оказывается, что он лжет и не лжет одновременно. Развитие математической логики особенно активизировалось в XX нашего века в связи с развитием вычислительной техники и программирования. Очевидно, что компьютерные науки носят прикладной характер и конечной их целью является создание и использование вычислительных систем. Здесь теоретические знания подтверждаются идеями воплощенными в железе ив получении результатов по обработке информации. Поэтому для инженера, программиста, математическая логика является наукой о правильных вычислениях, обоснованных алгоритмах, надежно функционирующих программах. Она не рассматривает вопросы проектирования программно изучает языки программирования как формальные системы и касается аспектов эффективности тех или иных алгоритмов. В учебном пособии излагается материал по математической логике, изучаемый в курсе Элементы математической логики и предназначенный для специальности 230115 Программирование в компьютерных системах.

5 Глава I. Алгебра логики
§1.1. Определение булевой функции Булевой функцией от п переменных x
1
,x
2
,...,x
n называется любая функция, в которой аргументы и функция могут принимать значение либо 0 либо 1, те. булева функция это правило по которому произвольному набору нулей и единиц (x
1
,x
2
,...,x
n
) ставится в соответствие значение 0 или 1. Значение 0 часто называют Ложью (False), а значение 1 – Истинной (True). Булевы функции называются также функциями алгебры логики, двоичными функциями и переключательными функциями. Булеву функцию от n переменных можно задать таблицей истинности, в которой наборы значений аргументов расположены в порядке возрастания их номеров сначала идет набор, представляющий собой двоичное разложение 0 этот набор имеет номер 0); затем идет набор, являющийся двоичным разложением 1, потоми т.д. Последний набор состоит из n единиц и является двоичным разложением числа 2 1
n

(такой порядок расположения наборов назовем лексикографическим порядком. Учитывая, что отсчет начинается с 0, а значение булевой функции может быть либо 0 либо 1, заключаем, что существует всего
2 2
n
различных булевых функций от n переменных. Таким образом, имеется, например, 16 булевых функций от двух переменных, 256 — от трех и т. д. Пример 1.1.1. (голосование. Рассмотрим устройство, фиксирующее принятие некоторой резолюции "комитетом трех. Каждый член комитета при одобрении резолюции нажимает свою кнопку. Если большинство членов голосуют зато резолюция принимается. Это фиксируется регистрирующим прибором. Таким образом, устройство реализует функцию f(x,y,z), таблица истинности которой имеет вид

6
x
0 0
0 0
0 1
1 1
y
0 0
1 1
1 0
0 1
z
0 1
0 0
1 0
1 1
f(x,y,z)
0 0
0 0
1 0
1 1 Булева функция также однозначно задается перечислением всех наборов, на которых она принимает значение 0, либо перечислением всех наборов, на которых она принимает значение 1. Полученную в примере функцию f можно также задать следующей системой равенств f(0,0,0) =
f(0,0,1) = f(0,1,0) = f(1,0,0) =0. Вектором значений булевой функции y=f(x
1
,x
2
,…,x n
) называется упорядоченный набор всех значений функции f, при котором значения упорядочены по лексикографическому порядку. Например, пусть функция трех переменных f задана вектором значений (0000 0010) и необходимо найти набор, на котором f принимает значение 1. Т.к. 1 стоит на 7 месте, а нумерация в лексикографическом порядке начинается сто необходимо найти двоичное разложение 6. Таким образом, функция f принимает значение
1 на наборе (110).
§1.2. Элементарные булевы функции Среди булевых функций особо выделяются так называемые элементарные булевы функции, посредством которых можно описать любую булеву функцию от любого числа переменных.
1. Булева функция f(x
1
,x
2
,…,x n
) принимающая значение 1 на всех наборах нулей и единиц называется константой 1, или тождественной единицей. Обозначение 1.
2. Булева функция f(x
1
,x
2
,…,x n
) принимающая значение 0 на всех наборах нулей и единиц называется константой 0, или тождественным нулем. Обозначение 0.

7
3. Отрицанием называется булева функция одной переменной, которая определяется следующей таблицей истинности x
0 1 f(x)
1 0 Обозначения

x,
x
. Запись

x читается не икс или отрицание икс.
4. Конъюнкцией называется булева функция двух переменных, которая определяется следующей таблицей истинности x
0 0
1 1 y
0 1
0 1 f(x
,
y)
0 0
0 1 Другие названия логическое умножение (произведение логическое и. Обозначения x

y, x

y, x

y, min(x,y). Запись x

y может читаться так икс и игрек или икс умножить на игрек.
5. Дизъюнкцией называется булева функция двух переменных, которая определяется следующей таблицей истинности x
0 0
1 1 y
0 1
0 1 f(x
,
y)
0 1
1 1 Другие названия логическое сложение (сумма логическое или. Обозначения x

y, max(x,y). Запись x

y может читаться так икс или игрек или сумма икс и игрек.
6. Импликацией называется булева функция двух переменных, которая определяется следующей таблицей истинности x
0 0
1 1 y
0 1
0 1 f(x
,
y)
1 1
0 1 Другое название логическое следование.

8 Обозначения x

y, x

y, x

y. Запись x

y может читаться так из икс следует игрек.
7. Эквивалентностью называется булева функция двух переменных, которая определяется следующей таблицей истинности x
0 0
1 1 y
0 1
0 1 f(x
,
y)
1 0
0 1 Обозначения x

y, x

y,.x

y. Запись x

y может читаться так икс эквивалентно игрек или икс равносильно игрек.
8. Суммой по модулю называется булева функция двух переменных, которая определяется следующей таблицей истинности x
0 0
1 1 y
0 1
0 1 f(x
,
y)
0 1
1 0 Другое название антиэквивалентность. Обозначения x

y, x+y. Запись x

y может читаться так икс плюс игрек.
9. Штрих Шеффера это булева функция двух переменных, которая определяется следующей таблицей истинности x
0 0
1 1 y
0 1
0 1 f(x
,
y)
1 1
1 0 Другое название отрицание конъюнкции, логическое «не-и». Обозначение x

y. Запись x

y может читаться так не икс или не игрек, икс и игрек несовместны», икс штрих Шеффера игрек.

9
10. Стрелка Пирса это булева функция двух переменных, которая определяется следующей таблицей истинности x
0 0
1 1 y
0 1
0 1 f(x
,
y)
1 0
0 0 Другое название отрицание дизъюнкции, логическое «не-или», функция
Вебба. Обозначение x

y; для функции Вебба - x

y. Запись x

y может читаться так ни икс и ни игрек, икс стрелка Пирса игрек. Замечание Символы

,

,

,

,

,

,

,

участвующие в обозначениях элементарных функций будем называть связками или операциями.
§1.3. Задание булевых функций посредством элементарных Если в логическую функцию вместо переменных подставить некоторые булевы функции, тов результате получается новая булева функция, которая называется суперпозицией подставляемых функций (сложная функция. С помощью суперпозиции можно получать более сложные функции, которые могут зависеть от любого числа переменных. Запись булевых функций через элементарные булевы функции будем называть формулой реализующей данную функцию. Пример 1.3.1. Пусть задана элементарная булева функция x

y. Подставим вместо x функцию x
1

x
2
. Получаем функцию трех переменных
(x
1

x
2
)

y. Если вместо переменной y подставить, например, x
3

x
4
, то получаем новую функцию от четырех переменных (x
1

x
2
)

(x
3

x
4
). Очевидно, что таким образом мы будем получать булевы функции, которые будут выражаться через элементарные булевы функции.

10 Забегая вперед, отметим, что любая булева функция может быть представлена как суперпозиция элементарных функций. Для более компактной записи сложных функций введем следующие соглашения 1) внешние скобки опускаются 2) сначала производятся операции в скобках 3) считается, что приоритет связок убывает в следующем порядке

,

,

,

,

. Для равносильных связок и оставшихся связок {

,

,

}, следует пока расставлять скобки. Примеры 1.3.2.
1. В формуле x

y

z скобки расставляются следующим образом ((x

y)

z), т.к. операция

сильнее операции

согласно нашему соглашению.
2. В формуле x

y

z

x скобки расставляются следующим образом
((x

y)

(z

x))
3. В формуле (x

y)

z

xy

z скобки расставляются следующим образом
((x

y)

(z

((xy)

(

z)))).
4. Формула x

y

z, следуя нашему соглашению, записана некорректно, т.к. расстановка скобок приводит к двум разным функциями. Существенные и несущественные переменные Булева функция y=f(x
1
,x
2
,…,x
n
) существенно зависитот переменной x
k
, если существует такой набор значений a
1
,a
2
,…,a
k-1
, a
k+1
,a
k+2
,…,a
n
, что f(a
1
,a
2
,…,a
k-1
,0,a
k+1
,a
k+2
,…,a
n
)

f(a
1
,a
2
,…,a
k-1
,1,a
k+1
,a
k+2
,…,a
n
). В этом случае x
k называют существенной переменной, в противном случае x
k называют несущественной (фиктивной) переменной. Другими словами, переменная является несущественной, если ее изменение не изменяет значения функции. Пример 1.4.1. Пусть булевы функции f
1
(x
1
,x
2
) и f
2
(x
1
,x
2
) заданы следующей таблицей истинности

11
x
1
x
2
f
1
(x
1
,x
2
)
f
2
(x
1
,x
2
)
0 0
0 1
0 1
0 1
1 0
1 0
1 1
1 0 Для этих функций переменная x
1
— существенная, а переменная x
2 несущественная. Очевидно, что булевы функции не изменяют свои значения путем введения (или удаления) несущественных переменных. Поэтому, в дальнейшем булевы функции рассматриваются с точностью до несущественных переменных (в примере можно записать f
1
(x
1
,x
2
)=x
1
, f
2
(x
1
,x
2
)=

x
1
).
§1.5. Таблицы истинности. Эквивалентные функции Зная таблицы истинности для элементарных функций, можно вычислить таблицу истинности той функции, которую реализует данная формула. Пример 1.5.1. F
1
=x
1

x
2

(x
1

x
2

x
1

x
2
) x
1
x
2
x
1

x
2

x
1

x
2
x
1

x
2

x
1

x
2
x
1

x
2
F
1 0
0 0
0 0
0 0
0 1
0 1
1 0
1 1
0 1
0 1
0 1
1 1
0 0
0 1
1 Таким образом, формула реализует дизъюнкцию. Пример 1.5.2. F
2
=x
1

x
2

x
1
x
1
x
2
x
1

x
2
F
2
=(x
1

x
2
)

x
0 0
0 1
0 1
0 1
1 0
0 1
1 1
1 1 Таким образом, формула реализует константу 1.

12 Пример 1.5.3. F
3
=((x
1

x
2
)

x
1
)

x
2
x
1
x
2
x
1

x
2
(x
1

x
2
)

x
1
(x
1

x
2
)

x
1
)

x
2 0
0 0
0 0
0 1
0 0
1 1
0 0
1 1
1 1
1 0
1 Таким образом, формула реализует дизъюнкцию. Булевы функции f
1
и f
2
называются эквивалентными, если на всяком наборе (a
1
, a
2
,…, a
n
) нулей и единиц значения функций совпадают. Обозначение эквивалентных функций следующее Согласно приведенным примерам 1-3, можно написать

x
1

x
2

(x
1

x
2

x
1

x
2
)=x
1

x
2
;

x
1

x
2

x
1
=1;

((x
1

x
2
)

x
1
)

x
2
=x
1

x
2
§1.6. Основные эквивалентности Приводимые эквивалентности часто оказываются полезными при оперировании с булевыми функциями. Ниже H, H
1
, H
2
,… означают некоторые булевы функции.
1. Закон двойного отрицания
H
H

2. Идемпотентность:
H&H=H, H

H=H.
3. Коммутативность H
1

H
2
=H
2

H
1
, где символ

означает одну из связок &,

,

,

,

,

4. Ассоциативность H
1

(H
2

H
3
)=(H
1

H
2
)

H
3
, где символ

означает одну из связок &,

,

,


13 5. Дистрибутивность
H
1
&(H
2

H
3
)=(H
1
&H
2
)

(H
1
&H
3
);
H
1

(H
2
&H
3
)=(H
1

H
2
)&(H
1

H
3
);
H
1
&(H
2

H
3
)=(H
1
&H
2
)

(H
1
&H
3
).
6. Законы де Моргана при
2
n

справедливы формулы
1 2
1 2
&
&... &
H
H
H
n
n
H
H
H


 
,
1 2
1 2
H & H &... & H
n
n
H
H
H

 

7. Правила поглощения
H
1

(H
2
&H
3)
=H
1
, H
1
&(H
2

H
3
)=H
1 8. Законы склеивания
1 2
1 2
1
&
&
H
H
H
H
H


,
1 2
1 2
1
(
) & (
)
H
H
H
H
H



9. Законы инверсий:
0
H
&
H
,
1
H
H



10. Правила операций с константами 0 и 1:
H

1=1, H&1=H, H

0=H, H&0=0. Для проверки истинности приведенных эквивалентностей (кроме законов де Моргана) достаточно построить соответствующие таблицы истинности. Отметим, что свойство ассоциативности операции позволяет распространить эту операцию для любого количества переменных. Так, например, запись у корректна, т.к. любая расстановка скобок приводит к одной и той же функции. Коммутативность операции позволяет менять местами переменные в формуле. Например, x

y

z

w=w

y

x

z. Докажем й закон де Моргана
1 2
1 2
&
&... &
H
H
H
n
n
H
H
H


 методом математической индукции. Справедливость формулы при
2
n

проверим непосредственно при помощи таблицы истинности

14 Пусть формула верна при n m

. Тогда при
1
n
m
 
имеем


1 2
1 1
2 1
&
&... &
&
&
&... применяем формулу при
2
n

, получаем


1 2
1
&
&... &
H
m
m
H
H
H




применяем формулу при n m

, получаем =


1 2
1 1
2 1
H
H
H
H
H
H
H
m
m
m




 



 Из принципа математической индукции заключаем, что формула верна при любом
2
n
