Элементы математической логики

Цель работы: Ознакомиться с логикой высказывания, формулами логики высказываний, с

нормальными формами формул и приведением к ДНФ, КНФ.

Порядок выполнения работы:

Практическая работа рассчитана на 2 часа аудиторных занятий, включающих в себя следующее:

1. Изучить:

- Логика высказываний. Формулы логики высказываний. Равносильность формул.

- Нормальные формы формул, приведение к ДНФ, КНФ.

- Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы.

- Минимизация в классе дизъюнктивных нормальных форм.

2. Решить упражнения к данному разделу. Выполнить каждый пункт упражнения согласно варианту. Вариант определяется как сумма двух последних цифр зачётной книжки, если количество заданий в пункте упражнения меньше, чем полученная цифра, то эта цифра делится пополам (берётся её целая часть).

3. Оформить отчет о проделанной работе в соответствии с требованиями.

4. Проработать контрольные задания СРС.

Требования к отчету:

Отчет по практической работе распечатывается в виде твердой копии и состоит из следующих пунктов:

Вариант индивидуального задания;

Результаты полученных решений заданий;

Ответы на контрольные задания СРС.

Методические указания

Булевой функцией f(x₁, x₂, ... , x_n) называется функция, которая принимает два значения 0 или 1 в зависимости от переменных х_i , каждая из которых может также принимать только два значения 0 или 1.

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

Таблица 3.1 – Представление булевой функции

Булева функция n переменных может иметь 2ⁿ наборов. Поскольку функция принимает только два значения, общее число булевых функций n переменных равно 2²ⁿ . Таким образом, функция одной переменой может иметь четыре значения: y = x; y = Øx (отрицание х); y = 0 (константа 0); y = 1 (константа 1).

Из них выделим функцию “отрицание x”(обозначается Øx). Эта функция представлена в таблице3.2.

Таблица 3.2 – Функция отрицание

Булевых функций двух переменных – 16. Те из них, которые имеют специальные названия, представлены в таблице 3.3.

Таблица 3.3 – Булевы функции двух переменных

x1 x2	x1Vx2	x1& x2	x1 x2	x1~x2	x1 Å x2	x1¯ x2	x1ï x2
0 0 0 1 1 0 1 1

В таблице 2.3 представлены следующие функции двух переменных:

x₁Vx₂ – дизъюнкция;

x₁& x₂ – конъюнкция;

x₁Éx₂ – импликация;

x₁~x₂ – эквивалентность;

x₁Å x₂ – сложение по модулю 2;

x₁¯x₂ – стрелка Пирса;

x₁ï x₂ – штрих Шеффера.

Формула логики булевых функций определяется индуктивно следующим образом:

1. Любая переменная, а также константы 0 и 1 есть формула.

2. Если A и B – формулы, то ØA, AVB, A&B, A É B, A ~ B есть формулы.

3. Ничто, кроме указанного в пунктах 1–2, не есть формула.

Пример:

Выражение (ØxVy)&((y É z) ~ x) является формулой.

Выражение Øx&y É z Ø ~x не является формулой.

Часть формулы, которая сама является формулой, называется подформулой.

Пример: x&(y Éz) – формула; y Éz – ее подформула.

Равносильные преобразования формул

В отличие от табличного задания представление функции формулой не единственно. Например, две различные формулы

Øx₁VØx₂ и Ø(x₁&x₂)

реализуют одну функцию – штрих Шеффера.

Две формулы, реализующие одну и ту же функцию, называются равносильными.

Равносильность формул A и B будем обозначать следующим образом: A º B.

Дата добавления: 2015-07-26; просмотров: 319; Нарушение авторских прав

Мы поможем в написании ваших работ!