Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

12 февраля 2001 г.

Рассмотрим функции от нескольких переменных, у которых множество определения и множество значений состоит из двух чисел . Эти функции называются функциями двузначной логики, булевыми функциями или функциями алгебры логики. Множество всех таких функций обозначается . Любую такую функцию можно задать таблицей:

,

где слева расположены все возможные наборы значений переменных (всего из будет ), а справа значение функции на этом наборе (0 или 1). Следовательно всего таких функций от переменных будет , это число обозначается через . Т.е. мы видим, что число таких функций хотя и конечно при любом , очень быстро растет, действительно . Рассмотрим подробно функции от одной и от двух переменных.

1) , здесь всего будет 4 функции, напишем таблицу для каждой из них:

.

Здесь 0 - это нулевая функция; - это тождественная функция; - это отрицание ; 1 – это единичная функция.

2) , здесь функций будет уже 16, все мы выписывать не будем, а выпишем только некоторые:

Здесь функция называется конъюнкцией или логическим И (умножением); - дизъюнкция или логическое ИЛИ (сложение); - логическое исключающее ИЛИ или просто сумма по модулю 2; - импликация; - штрих Шеффера.

Определение. Функция называется существенно зависящей от переменной ( называется существенной переменной), если существуют два набора значений переменных, отличающихся только значением переменной , такое, что значения функции на этих наборах разные, т.е. .

Определение. Переменная называется несущественной переменной, если она не является существенной, т.е. если для любых двух наборов и имеем .

Пример. Конъюнкция существенно зависит от переменной , т.к. . Конъюнкция также существенно зависит от переменной , т.к. . Аналогично показывается, что и дизъюнкция, и сумма по модулю 2, и импликация, и штрих Шеффера существенно зависят от обеих переменных.

ОТБРАСЫВАНИЕ НЕСУЩЕСТВЕННОЙ ПЕРЕМЕННОЙ

Пусть дана функция , которая несущественно зависит от переменной , тогда если , то , т.е. ее таблица имеет следующий вид

Вычеркнем все вторые наборы (у которых ) и -й столбец, получим новую функцию , т.ч. , ее таблица:

Говорят, что функция получилась из функции отбрасыванием несущественной переменной .

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

Определение. Две функции и называются равными, если одна из них получается из другой в результате добавления и (или) отбрасывания несущественной переменной (переменных).

Пример. Пусть дана функция , несущественно зависящая от переменной , отбросим ее,

получим функцию , добавим несущественную переменную , получим функцию , тогда будем иметь, что (хотя таблицы у них и разные!).

ФОРМУЛЫ

Пусть дано некоторое множество функций . Определим понятие формулы над множеством индуктивно:

1) сами функции являются формулами над ;

2) пусть каждый из объектов - либо переменная, либо формула над , тогда объект тоже будет формулой над .

Т.е. для образования новых формул достаточно в уже имеющихся формулах переменные заменять на другие формулы.

Пример. Пусть , тогда , , будут формулами над , а не будет.

ЗНАЧЕНИЕ ФОРМУЛЫ НА НАБОРЕ ПЕРЕМЕННЫХ

Пусть дана формула и набор значений переменных , определим значение формулы индуктивно:

1) значение переменной на наборе равно ;

2) пусть мы уже определили значения , тогда

.

Т.к. мы может определить значение формулы на любом наборе переменных, то любая формула выражает какую-то функцию.

Определение. Две формулы называются эквивалентными (равными), если они выражают равные функции.

Рассмотрим множество функций . Напишем несколько примеров эквивалентных формул над :

Введем функцию , тогда будем иметь, что , действительно, в обоих случаях будем иметь: .

Введем некоторые соглашения по записи формул. Знак логического умножения можно не писать, как обычное умножение в алгебре. Для однотипных ассоциативных операций внутренние скобки писать не будем, т.е. вместо будем писать просто . Внешние скобки также можно опускать и вместо будем писать .

Также введем некоторые сокращения:

СДНФ

Рассмотрим формулу . Она равна единице только на одном наборе, а именно на наборе .

Теорема (о разложении функции по множеству переменных). Пусть дана функция и число , тогда , что будет формулой над множеством функций .

Доказательство. Возьмем произвольный набор . Найдем значение этой формулы на этом наборе. Если , то . Если , то , т.е.

.

Рассмотрим отдельно два частных случая: при и .

1) . Мы получим разложение функции по первой переменной:

.

2) . , т.к. - это либо 0, либо 1, то нам достаточно «суммировать» по наборам таких, что , т.е.

. Это уже будет формулой над множеством . Такое представление функции называется совершенной дизъюнктивной нормальной формой.

Примеры:

, где - это следующая функция:

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов лекций