Множества, отображения, логика



страница3/6
Дата26.11.2012
Размер0.77 Mb.
ТипДокументы
1   2   3   4   5   6

4.5. Логические операции и формулы. Булевы функции можно рассматривать как логические операции над величинами, принимающими значения 0 или 1. Отрицание — это одноместная операция, а конъюнкция, дизъюнкция, импликация и эквиваленция — двухместные операции. При этом выражения X, Y, , XY, XВ, АВ, АВ являются логическими формулами.

Более сложные формулы получаются замещением входящих в них переменных другими логическими формулами, которые обычно заключаются в скобки. Например, положив и , из формулы получаем формулу . Каждая формула определяет булеву функцию. Ее значения при различных значениях переменных А, В, С определяются по таблице истинности, построенной на основании таблиц истинности, приведенных в п. 4.2 и п. 4.3.


A

B

C





gif" name="object64" align=absmiddle width=97 height=19>

1

1

1

0

1

1

1

1

0

0

0

0

1

0

1

0

0

0

1

0

0

0

0

0

0

1

1

1

1

1

0

1

0

1

0

1

0

0

1

1

0

1

0

0

0

1

0

1


Равносильность функций (и определяющих их формул) понимается в смысле равносильности отображений (см. п. 3.2).

4.6. Булева алгебра — это тройка B = [F  Z2  ], где F — множество всех булевых функций,  = {¯, , } — множество трех логических операций: отрицание, конъюнкция, дизъюнкция. Из определения логических операций легко следует справедливость тождеств (свойств) булевой алгебры:

коммутативность

= , = ;

ассоциативность

= , = ;

дистрибутивность

= , = ;

поглощение нуля

;

умножение на единицу

;

свойства отрицания

, .

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

, (законы де Моргана),

(законы поглощения),

(законы идемпотентности),

а также тождества:

,

,

, , , ,

и т.д.

4.8. С помощью таблиц истинности доказывается, что

= :

X



Y








Y

1

1

1




0

1

1

1

0

0




0

0

0

0

1

1




1

1

1

0

1

0




1

1

0


Аналогично доказывается, что :


X



Y




X



Y



Y



X

1

1

1




1

1

1

1

1

1

1

1

0

0




1

0

0

0

0

1

1

0

0

1




0

1

1

0

1

0

0

0

1

0




0

1

0

1

0

1

0


4.9. Предикат — это предложение с одной или несколькими переменными, которое становится высказыванием, если переменные принимают конкретные значения. Предикат с n переменными называется n-местным. Например, предложение «Число х — положительное» — одноместный предикат, предложение «х > у» — двуместный предикат, предложение «» — n-местный предикат.

4.10. Множество истинности предиката — это множество всех значений переменной , при которых данный предикат является истинным высказыванием.

Строго говоря, предикат — это отображение

: D  Z2,

некоторого подмножества в множество Z2; при этом D называется областью определения предиката. Тогда множество истинности предиката — это полный прообраз D элемента 1  Z2.

Множество истинности предиката будем обозначать с помощью квадратных скобок: [].

4.11. Связь логики с теорией множеств. Из 4.10, 4.2, 2.14 следует, что .

4.12. Пусть даны два n-местных предиката и , определенных на множестве . Тогда из 4.10, 4.3, 2.11 и 2.12 следует

, ,

или, проще,

, .

Для импликации и эквиваленции получаем:

,



.

4.13. Кванторы. Переменную в предикате можно связать квантором общности или квантором существования.

Квантор общности произошел от английского слова All (все), обозначается символом  и читается «любой, всякий, каждый»; символ  есть просто перевернутая буква А.

Квантор существования произошел от английского слова Exist (существовать), обозначается символом  и читается «существует, имеется, найдется»; символ  — это перевернутая буква Е.

Пример 1. Высказывание A = «Каждый день Красавице дарят розы» может быть формализовано как двуместный предикат P(x, y) = «В день х человек y дарит розы Красавице», у которого переменная х связана квантором общности , а на переменную у навешан квантор существования :

А = (х) (у) Р(х, у).■

Пример 2. Пусть «» 3-местный предикат, определенный на множестве . Связав любую переменную квантором (общности или существования), мы получим 2-местный предикат, например, .■

Вообще, если навесить по одному квантору на k переменных n-местного предиката, , то n-местный предикат превратится в (nk)-местный. Причем 0-местный предикат — высказывание.

Запись с восклицательным знаком !у читается «существует единственный у», а высказывание (х) (!у) Р(х, у) читается «для любого х существует и притом единственный у, для которого Р(х, у)».

Упражнение. Приведите пример, показывающий неравносильность высказываний (х) (у) Р(х, у) и (у) (х) Р(х, у).
1   2   3   4   5   6

Похожие:

Множества, отображения, логика iconФакультет
Отображения множеств. Счетные и несчетные множества. Функции множества. Мера множества. Измеримые множества и функции. Интеграл Лебега....
Множества, отображения, логика iconУчебно-методическое пособие Саранск 2012 Отображения. Функции Сведения из теории
Пусть даны некоторые множества и. Бинарное соответствие из в называется отображением множества в множество, если
Множества, отображения, логика iconМатематический анализ
Множества. Декартово произведение двух множеств. Отображения функции, обратная функция. Эквивалентность множеств. Счетность множества...
Множества, отображения, логика iconПрограмма курса дифференциальная топология и риманова геометрия
Топология, топологическое пространство. Гомеоморфизм, сравнение топологий. Открытые и замкнутые множества. Внутренность, замыкание...
Множества, отображения, логика iconГруппы: мк-301, мт-301
Понятия множества и отображения, способы задания множеств. Алгебра множеств и подмножеств. Теорема об отображении множества самого...
Множества, отображения, логика icon1 Содержание дисциплины
Множества, подмножества. Булевы операции над множествами и их свойства. Законы Д’Моргана. Отношения, функциональные отношения, отображения....
Множества, отображения, логика iconМножества и операции со множествами. Понятие множества и мультимножества
Цель таких описаний отразить важнейшие (атрибутные) свойства множества, а именно: разли­чимость всех частей множества, неупорядоченность...
Множества, отображения, логика iconПрограмма государственного экзамена Направление подготовки 230400 «Прикладная математика»
Отображения. Инъективные, сюръективные и биективные отображения. Теорема о произведении (композиции) отображений. Критерий существования...
Множества, отображения, логика icon1-й и 2-й семестры Множества и отображения
Множество и его элементы. Примеры множеств. Отношение включения и его свойства. Операции над множествами: пересечение, объединение,...
Множества, отображения, логика iconРоберт столл множества. Логика. Аксиоматические теории

Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org