Математическая логика и теория алгоритмов. Галуев Г.А. - 5 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 5 из 64
© 2003 Галуев Геннадий Анатольевич
Дизъюнкция. Дизъюнкция высказываний А и В обозначается А
∨
В (читается «А
или В»). Высказывание А
∨ В ложно тогда и только тогда, когда ложны оба высказы-
вания А и В.
Импликация. Импликация высказываний А и В обозначается А→В (читается «если
А то В»). Высказывание А→В ложно тогда и только тогда, когда А, называемое посыл-
кой импликации, истинно, а высказывание В, называемое заключением импликации,
является
ложным. От используемого в обыденной жизни понятия следования данная
операция отличается тем, что А и В не обязательно должны быть содержательно свя-
занными высказываниями и поэтому в математической логике высказывание «Если
Земля стоит на трёх слонах, то Таганрог основан Петром I» считается истинным.
Эквивалентность. Эквивалентность высказываний А и В обозначается А↔
В (чи-
тается А тогда и только тогда, когда В) и имеет значение «истина» только при совпа-
дающих значениях истинности высказываний А и В.
Введём понятие пропозиционной формы (формулы логической) с помощью
следующего индуктивного
о
о
п
п
р
р
е
е
д
д
е
е
л
л
е
е
н
н
и
и
я
я
:
:
а) Пропозиционные буквы есть
пропозиционные формы
б) Если А и В пропозиционные формы, то (
⎤
А), (А
&
В), (А ∨ В), (А
→
В), (А
↔
В) тоже
пропозиционные формы.
Пропозиционными формами являются те и только те выражения, которые полу-
чены в соответствии с а) и б).
Каждому распределению истинностных значений пропозиционных букв соответ-
ствует некоторое истинностное значение пропозиционной формы, состоящей из этих
букв. В свою очередь, каждая пропозиционная форма определяет некоторую истин-
ностную (булеву, логическую) функцию
, которая может быть представлена таблицей
истинности. Если в пропозиционной форме имеется n различных пропозиционных
букв, то число возможных распределений истинностных значений этих букв равно 2
n
и столько же истинностных значений имеет пропозиционная форма. Истинностной
функцией (булевой функцией) n аргументов называется всякая функция n аргумен-
тов, которая принимает значение И (1) или Л(0), если аргументы её пробегают те же
значения.
Так как каждая булева функция n аргументов может быть представлена как 2
n
компонентный вектор, компоненты которого принимают 0 или 1, то обще количество
различных булевых функций n аргументов равно
n
2
2 .
Тогда при n=0 имеем 2 различные функции F
1
=1 (константа единицы) и F
2
=0
(константа нуля).
При n=1 имеем 4 различные функции F
1
(X)=1, F
2
(X)=0, F
3
(X)=X, F
4
(X)=⎤X.
При n=2 имеем 16 различных булевых функций:
X
1
X
2
F
1
F
2
F
3
F
4
F
5
F
6
F
7
F
8
F
9
F
10
F
11
F
12
F
13
F
14
F
15
F
16
0 0 1 0 0 0 1 1 0 0 1 1 0 1 1 1 0 0
0 1 1 0 0 1 1 0 0 1 1 0 1 1 0 0 0 1
1 0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 1 0
1 1 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0
Эти функции имеют свои стандартные обозначения: F
1
(X
1
,X
2
)=1, F
2
(X
1
,X
2
)=0,
F
3
(X
1
,X
2
)=X
1
, F
4
(X
1
,X
2
)=X
2
, F
5
(X
1
,X
2
)=⎤X
1
, F
6
(X
1
,X
2
)=⎤X
2
, F
7
(X
1
,X
2
)=X
1
&X
2
,
F
8
(X
1
,X
2
)=X
1
∨
X
2
, F
9
(X
1
,X
2
)=X
1
→X
2
, F
10
(X
1
,X
2
)=X
1
↔X
2
, F
11
(X
1
,X
2
)=X
1
⊕X
2
, F
12
(X
1
,X
2
)=X
1
⎜X
2
(штрих Шеффера), F
13
(X
1
,X
2
)=X
1
↓X
2
(стрелка Пирса), F
14
(X
1
,X
2
)=X
2
→X
1
,
F
15
(X
1
,X
2
)=X
1
←X
2
(функция запрета X
1
по X
2
), F
16
(X
1
,X
2
)=X
2
←X
1
(функция запрета X
2
по X
1
).

Страницы