ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 9331
Скачиваний: 24
46
19)
(
)
)
x
(
j
)
x
(
j
x
)
x
(
j
)
x
(
j
)
x
(
j
j
x
1
0
1
0
1
0
−
+
=
⋅
+
⋅
;
20)
)
x
(
J
))
1
i
(
x
(
J
)
i
x
(
J
i
0
0
=
−
÷
÷
÷
,
i
=1, 2, …, k–1.
II. При каких значениях k (k
≥3) функции x
2
, x
3
и x
4
попарно
различны?
III. Для заданного k представить функцию f в первой и вто-
рой формах (полученные выражения упростить)
1)
f=~ x, k=4;
2)
f=–j
0
(x), k=5;
3)
f=2J
1
(x), k=6;
4)
f=J
2
(x
2
+x), k=5;
5)
f=(~x)
2
+x, k=4;
6)
f=3j
1
(x) – j
3
(x), k=4;
7)
f=x
1
+2x
2
, k=3;
8)
f=max (x
1
, x
2
), k=3;
9)
f= x
1
÷ x
2
2
, k=3;
10)
f= x
1
2
⋅ x
2
, k=3.
47
5
ЛОГИКА
ВЫСКАЗЫВАНИЙ
Логика высказываний является разделом математической
логики, в котором рассматриваются сложные предложения, по-
лучающиеся из предложений, принимаемых за элементарные вы-
сказывания, соединенных союзами «И», «ИЛИ», «ИЛИ…ИЛИ»,
«ЕСЛИ…, ТО», «ТОГДА И ТОЛЬКО ТОГДА, КОГДА» и при-
соединением к ним частицы «НЕ».
Высказывание
– это предложение, которое может оцени-
ваться по его истинности, а не с точки зрения его содержания.
Неделимое высказывание называется
элементарным
.
Сложные высказывания
соединяются логическими связя-
ми или связками «И», «ИЛИ», «ИЛИ…ИЛИ», «ЕСЛИ…, ТО»,
«ТОГДА И ТОЛЬКО ТОГДА, КОГДА» и частицей «НЕ».
Логика высказываний занимается не смыслом высказыва-
ния, а анализирует, истинно оно или ложно.
Про истинное предложение говорят, что его логическим
значением является
истина
, а про ложное – что его логическим
значением является
ложь
.
Примеры элементарных высказываний:
«пять – нечетное число», «трава голубая», «Томск – столица
Сибири».
Следующие предложения не являются высказываниями:
«уходя, гасите свет», «сколько Вам лет?» и т.п. Такого типа вы-
ражения в логике высказываний не рассматриваются.
В естественном языке союзы и частица «НЕ» имеют не
вполне отчетливое значение, а некоторые из них могут употреб-
ляться в различных смыслах. Например, союз «ИЛИ» может быть
разделительным (как в фразе «выбирай, он или я») или неразде-
лительным (как в фразе «от шума или света я проснулся», в кото-
рой не исключается, что «я проснулся» от общих причин).
В логике высказываний принято ставить в соответствие вы-
сказываниям буквы и называть их логическими переменными.
Рассмотрим выражение:
Если в следующее воскресенье бу-
дет плохая погода и я не достану билет на концерт, то я схожу
в кино или буду готовиться к зачету
. Разобьем это высказывание
на элементарные высказывания и обозначим их буквами:
а – в следующее воскресенье будет плохая погода;
48
b – я достану билет на концерт;
c – я схожу в кино;
d – буду готовиться к зачету.
Выражение примет следующий вид:
Если a и не b, то c или d
Для сокращения письма связки обозначаются соответст-
вующими знаками: ¬, ٨, ٧, ~,
⊗, →. Смысл операций (связок) ус-
танавливается соответствующими таблицами, поскольку опреде-
лить операцию – это значит определить истинность высказыва-
ния для каждого значения логических переменных.
1.
Отрицание
¬а, ā,
не
а
; Ложь обозначим буквой Л, ис-
тину – И.
а
ā
Л
И
И
Л
2.
Конъюнкция
а ٨ b
, (
a
и
b
, (
a &
b
), (
a
конъюнкция
b
).
Эту операцию называют логическим умножением.
a b a ٨ b
Л Л
Л И
И Л
И И
Л
Л
Л
И
Пример: 5 > 2 и 7 четное число. Оценим истинность данного
высказывания. 5 > 2 – истина; 7 четное число – ложь; в результа-
те исходное выражение ложно.
3.
Дизъюнкция
a ٧ b
, (
a
или b
). Операция логического сло-
жения.
a b a ٧ b
Л Л
Л И
И Л
И И
Л
И
И
И
49
4.
Импликация a → b
(
если a, то b
).
a b
a → b
Л Л
Л И
И Л
И И
И
И
Л
И
5.
Эквивалентность a ~ b
, (
a
эквивалентно
b
),
(a если и
только если b).
a b
a ~ b
Л Л
Л И
И Л
И И
И
Л
Л
И
6.
Дизъюнкция с исключением
⊕
; (или a или b).
a b
a
⊗ b
Л Л
Л И
И Л
И И
Л
И
И
Л
Рассмотрим предыдущий пример. В соответствии с введен-
ными операциями он будет выглядеть:
а ٨ ¬ b → c ٧ d.
Вычислим истинность этого высказывания. Для этого необ-
ходимо построить таблицу истинности от четырех переменных, в
которой будет 2
4
строк, и вычислить значение на каждом наборе
переменных.
50
a b c d a
٨ ¬ b → c ٧ d
Л Л Л Л
И
Л Л Л И
И
Л Л И Л
И
Л Л И И
И
Л И Л Л
И
Л И Л И
И
Л И И Л
И
Л И И И
И
И Л Л Л
Л
И Л Л И
И
И Л И Л
И
И Л И И
И
И И Л Л
И
И И Л И
И
И И И Л
И
И И И И
И
Это высказывание ложно только в одном случае, когда вы-
сказывания а = И, b = Л, c = Л, d = Л.
Логика высказываний не дает методов вычисления истинно-
сти элементарных высказываний, но хорошо определяет истин-
ность сложных высказываний.
Если высказывание сложное и стоит задача определить ис-
тинность высказывания, то необходимо построить формулу или
систему формул. Далее необходимо определить множество пра-
вильных формул, затем выполнить действия и получить ответ.
1.
Определим алфавит, т.е. символы, которыми можно поль-
зоваться:
a, b, c,…, x, y, z, ٨, ٧, ¬, →,
⊕
, ), (.
2.
Будем утверждать, что
a, b, c,…, x, y, z
– формулы.
3.
Если
a, b
– формулы, то формулами являются выражения:
(¬а), (a
∨
b), (a
∧
b), (a
→
B), (a~b), (a
⊕
b).
4.
Других формул нет.
Примеры:
((a
→ b) ∧ (¬(с ∨ а))), ((а ∨ (¬b)) ⊕ a) – формулы.
(а¬b)– не является формулой.