Лекция №8
| Вид материала | Лекция |
- «Социальная стратификация и социальная мобильность», 46.19kb.
- Первая лекция. Введение 6 Вторая лекция, 30.95kb.
- Лекция Сионизм в оценке Торы Лекция Государство Израиль испытание на прочность, 2876.59kb.
- Текст лекций н. О. Воскресенская Оглавление Лекция 1: Введение в дисциплину. Предмет, 1185.25kb.
- Собрание 8-511 13. 20 Лекция 2ч режимы работы эл оборудования Пушков ап 8-511 (ррэо), 73.36kb.
- Концепция тренажера уровня установки. Требования к тренажеру (лекция 3, стр. 2-5), 34.9kb.
- Лекция по физической культуре (15. 02.; 22. 02; 01. 03), Лекция по современным технологиям, 31.38kb.
- Тема Лекция, 34.13kb.
- Лекция посвящена определению термина «транскриптом», 219.05kb.
- А. И. Мицкевич Догматика Оглавление Введение Лекция, 2083.65kb.
Лекция №8.
Алгебры высказываний. Предикаты и операции над ними.
§8.1. Основные логические операции и их свойства.
В математической логике изучаются высказывания и различные и связи между ними. При этом понятие высказывания считается основным, неопределяемым понятием. В качестве пояснения говорят лишь, что высказывание – это утверждение, относительно которого известно, истинно оно или ложно.
Если высказывание а истинно или ложно, то говорят, что оно имеет значение «и» или «л» и пишут
аи или ал.
Высказывания а и b, имеющие одинаковые значения, называются равносильными, что обозначается в виде
аb
Очевидно, что отношение равносильности высказываний является отношением эквивалентности на любом множестве высказываний М, и потому М разбивается на два класса высказываний – на класс истинных и класс ложных высказываний.
В обычной речи мы из определенных высказываний а, b с помощью различных связок можно образовывать новые высказывания, например «а и b» «а или b» «если а то b», «неверно, что а». В математической логике эти высказывания обозначаются в виде
ab (ab), ab, a->b,a (a)
и называются конъюнкцией, дизъюнкцией, импликацией и отрицанием высказывания а.
Таблица 8.1.1
-
a
b
ab
ab
a->b
a
и
и
и
и
и
л
и
л
л
и
л
л
л
и
л
и
и
и
л
л
л
л
и
и
В высказываниях ab, ab, a и b называются членами, или компонентами, соответственно конъюнкции и дизъюнкции ; в высказывании а->b а называют посылкой, b – заключением импликации.
Обозначим через = {и, л}. Тогда таблица 8.1.1 может служить определением операций , , ->, на множестве .
При этом операции , , обладают следующими свойствами:
- Операции , коммутативны, ассоциативны, идемпотентны, дистрибутивны одна относительно другой и связаны законами поглощения
a(ab)a,
a(ab)a;
_
- Операция отрицания – инволютивна (т.еа = а) и связана с операциями , законами де Моргана
___ ___
аb а b, аb = а b
и соотношениями
а а л, а а и.
Отсюда следует, что алгебра (, , ) является булевой алгеброй. В ней роль 1 и 0 играют соответственно элементы и, л.
Определение 8.1.2. Двухэлементная булева алгебра (, , ) называется алгеброй высказываний.
Из таблицы 8.1.1 видно, что импликация (->) также являются операцией на множестве и обладает рядом свойств, связывающих её с другими операциями:
a -> b b ->a (закон контрапозиции),
a -> (b -> a) и,
ab -> b и,
a -> b a b и другие.
§ 8.2. Предикаты и операции над ними.
Пусть М – произвольное непустое множество, и n N {0}. Мn — n-нная декартова степень множества М.
Определение 8.2.1. Любое отображение
Р: Мn ->
называется n-местным предикатом на множестве М.
n-местный предикат, содержащий переменные x1, …, xn обозначим через Р(x1, …,xn). Переменные x1, …,xn принимают значения из множества М.
Если – значение предиката Р(x1,…,xn) при x1 = a1 , …, xn = an, то будем писать
P(a1, …, an) =
Пример 8.2.2.
M = N, n = 1.
Тогда предложение «Х есть простое число» есть 1-местный предикат на множестве N. Обозначим это предложение через Р(х). Тогда Р: N -> ,
где
Р(х) = и, если х простое число,
л, если х – не является простым числом.
Пример 8.2.3.
M = N, n = 3.
Тогда предложение
«Число z является суммой чисел x, y»
есть 3-местный предикат на множестве N.
Обозначим это предложение через P(x,y,z)
Тогда P: N3 -> .
P(x,y,z) = и, если z = x + y,
л, если z x + y
Замечание 8.2.4. Любой n-местный предикат Р(x1, …, xn) на множестве М при фиксации переменных x1, …, xn превращается в высказывание.
Замечание 8.2.5. Под 0-местным предикатом понимается произвольное высказывание.
При этом нуль-местных предикатов ровно два – истинный и ложный.
Множество М0 - одноэлементно, (содержит единственную последовательность элементов множества М длины нуль).
Поэтому М0 -> Ω отождествляются с элементами множества Ω (поэтому нуль-местных предикатов ровно два – истинный и ложный).
Замечание 8.2.6. По n-местному предикату Р(x1, …, xn) естественным образом определяется n-арное отношение R на множестве М: (a1, …, an) Мn положим
(a1, …, an) R Р(a1, …, an) и.
Тем самым устанавливается взаимооднозначное соответствие между множествами n-арных отношений и всех n-местных предикатов на множестве М.
В связи с этим множество М с системой определенных на нем предикатов называется, как и множество М с системой отношений, моделью сигнатуры и обозначается М().
Опишем некоторые способы, позволяющие получать из одних предикатов на множестве М другие предикаты и там же на множестве М.
1. Пусть Р(x1, …, xn) произвольный предикат на М. Заменив в нем х1 некоторым элементом а М, мы получим новый, (n-1)-местный предикат на М, который будем обозначать в виде
Р(а, x2, …, xn)
или каким-либо иным образом, например
q(x2, …, xn).
Аналогично, новые предикаты можно получать из предиката Р(x1, …, xn), заменяя в нем какую либо другую переменную или даже несколько переменных элементами из М. Ясно, что заменив к переменных, получим (n-к)-местный предикат .
Пример 8.2.7.