МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ
(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)
Лекции
МАТЕМАТИЧЕСКАЯ ЛОГИКА
4 семестр
Лектор
Москва, 2009/2010
Лекция № 1.
БУЛЕВЫ ФУНКЦИИ (ФАЛ).
Рассмотрим множество 
.
Фиксированный набор будем обозначать 
. Их число 
.
Рассмотрим множество 
.
Определение 1.
Функция, дающая однозначное отображение 
называется булевой или функцией алгебры логики (ФАЛ).
Теорема 1.
Число булевых функций, зависящих от n аргументов, равно 
.
4
|
|
|
|
|
|
0 | 0 |
| 0 | 0 |
|
0 | 0 |
| 0 | 1 |
|
|
|
|
|
| |
1 | 1 |
| 1 | 0 |
|
1 | 1 |
| 1 | 1 |
|
3
Элементарные булевы функции.
Функции-константы:
Функции одного переменного:
x |
|
|
0 | 0 | 1 |
1 | 1 | 0 |
|
|
|
|
|
|
|
|
|
конъюнкция | дизъюнкция | импликация | эквивалентность би-импликация | сложение по модулю 2 | стрелка Пирса | штрих Шеффера | ||
0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |
0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 |
1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
Определение 2.
Функция F, полученная из множества функций 
называется суперпозицией этих функций, если она получена с применением двух правил: переименованием аргументов и подстановкой функций вместо аргументов.
Выражение одних булевых функций через другие.
Утверждение 1.
Закон де Моргана.
4
|
|
|
|
|
|
|
|
0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
3
Утверждение 2.
Аналог законов де Моргана.
4
|
|
|
|
|
|
|
0 | 0 | 1 | 1 | 0 | 1 | 0 |
0 | 1 | 1 | 0 | 1 | 0 | 1 |
1 | 0 | 0 | 1 | 1 | 0 | 1 |
1 | 1 | 0 | 0 | 1 | 0 | 1 |
3
Свойства.
1. Коммутативность:
НО! 
2. Ассоциативность:
НО! 
3. Дистрибутивность:
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 |
