Лекция 2-3 Алгебра высказываний. Логические функции. Законы булевой алгебры
Алгебра логики — раздел математической логики, изучающий строение сложных логических высказываний и способы установления их истинности с помощью алгебраических методов.
Чтобы понять сущность алгебраического подхода к логике, вспомним обычную школьную алгебру, которую можно назвать алгеброй арифметики. Основные ее объекты — формулы, состоящие из букв, знаков арифметических операций и скобок. Буквы обозначают переменные, которые могут принимать числовые значения. С формулами производят процедуры двух видов: вычисления и преобразования. Вычисление формулы заключается в том, что вместо букв подставляются числа; знаки указывают действия, а скобки — в каком порядке эти действия с подставленными числами надо выполнить. Каждая формула задает некоторую арифметическую функцию; число аргументов (переменных) этой функции равно числу различных букв в формуле. Множество различных формул и задаваемых ими функций бесконечно; однако все они строятся с помощью небольшого числа элементарных функций, называемых арифметическими операциями — сложения, умножения и т. д. Преобразование формулы заключается в том, что исходная формула F1 или ее часть заменяется другой формулой, в результате чего получается новая формула F2, которая эквивалентна F1 в следующем смысле: формулы F1 и F2 задают одну и ту же функцию, т. е. при любых значениях переменных вычисления F1 и F2 дают один и тот же результат. Преобразования формул производятся на основании законов арифметики (ассоциативного, коммукативного и дистрибутивного законов, равенства а - а = 0 и др.), а также полученных из них соотношений типа (а + b)2 = а2 + 2ab + b2 и т. д.
По аналогичным принципам строится и алгебра логики. Разница заключается в следующем. В формулах алгебры логики переменные являются логическими или двоичными, т. е. принимающими только два значения — "ложь" и "истина", которые обозначаются либо 0 и 1, либо Л и И, либо false и true. Знаки операций обозначают логические операции (логические связки). Каждая формула задает логическую функцию: функцию от логических переменных, которая сама может принимать только два логических значения. Любую логическую функцию можно задать таблицей, в левой части которой выписаны все возможные наборы значений ее аргументов , а правая часть представляет собой столбец значений функции, соответствующих этим наборам:
|
|
набор значений аргументов
| значение (0 или 1) функции
|
Число строк в такой таблице равно 2n — числу возможных наборов значений аргументов, т. е. числу различных комбинаций длины п из нулей и единиц. Число различных функций п переменных равно — числу возможных расстановок нулей и единиц в столбце с 2n строками.
Таблица функции f(x) одной переменной содержит всего две строки, а самих функций одной переменной — четыре :
| f(x)
| ||||
0 1
| 0 1
|
f(x)=x
(повторение)
константа 0
x
| f(x)
|
0 1
| 0 0
|
x
| f(x)
|
0 1
| 0 0
|
(отрицание)
константа 1
Таблица функции двух переменных содержит четыре строки, а самих функций двух переменных — шестнадцать (). Укажем наиболее важные из них. Пять функций соответствуют логическим связкам (см. перечень связок и обозначений для них в статье "Математическая логика"):
Таблица 1
Таблица 2
x1 | x2 | x1& x2 |
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
x1 | x2 | x1V x2 |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
Дизъюнкция
(ИЛИ)
Конъюнкция
(И)
x1 | x2 |
|
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
x1 | x2 |
|
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 1 | 1 |
Импликация
Таблица 3
Таблица 4
Эквивалентность
Импликация
Кроме того, часто употребляются ещё две функции двух переменных:
Таблица 5
Таблица 6
x1 | x2 |
|
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
x1 | x2 |
| |
0 | 0 | 0 | |
0 | 1 | 1 | |
1 | 0 | 1 | |
1 | 1 | 0 |
Штрих Шеффера
(НЕ-И)
Неравнозначность
(сложение по модулю два)
Таблица 7
x1 | x2 |
|
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 0 |
Стрелка Пирса
(НЕ-ИЛИ)
Стрелка Пирса
Вычислим эту функцию на наборе . (Логически это значит: определим значение истинности сложного высказывания (1) при условии, что составляющие его простые высказывания х1 и х2 истинны, а х3 — ложно.) Подстановка значений в формулу (1) дает
Вычислив эту формулу на остальных 7 наборах значений х1, х2, х3, полностью восстановим таблицу этой функции.
Таблица 8
x1
| x2
| x3
|
|
0
| 0
| 0
| 0
|
0
| 0
| 1
| 0
|
0
| 1
| 0
| 0
|
0
| 1
| 1
| 0
|
1
| 0
| 0
| 1
|
1
| 0
| 1
| 1
|
1
| 1
| 0
| 0
|
1
| 1
| 1
| 1
|
Таким образом, от функции, заданной в виде формулы (выражения), всегда можно перейти к табличному заданию. Ответ на обратный вопрос:
всегда ли от таблицы функции можно перейти к формуле — не столь однозначен и зависит от того, какие операции предполагается использовать в формулах. Формула, задающая функцию, фактически определяет ее через набор других функций, которые выбраны в качестве исходных и обозначены знаками операций. (В формуле (1) операциями являются конъюнкция, дизъюнкция, отрицание и импликация.)
Существуют наборы логических функций, с помощью которых можно выразить любые другие логические функции. Такие наборы называются функционально полными наборами или базисами. Наиболее известный и изученный базис — набор "И", "ИЛИ", "НЕ" (конъюнкция, дизъюнкция, отрицание). Множество всех логических функций, на котором определены эти три операции, называется булевой алгеброй; операции и формулы булевой алгебры также часто называют булевыми.
Функциональная полнота булевой алгебры означает, что переход от табличного задания к булевой формуле всегда возможен. Метод перехода заключается в следующем: для каждого набора значений переменных на котором функция равна 1, выписывается конъюнкция всех переменных; над теми переменными, которые в этом наборе равны 0, ставятся отрицания; все такие конъюнкции соединяются знаками дизъюнкции. Полученная формула называется совершенной дизъюнктивной нормальной формой (СДНФ) логической функции . СДНФ для каждой функции единственна, как говорят в математике, с точностью до перестановок переменных или конъюнкций. Это означает, что две различные СДНФ одной функции могут отличаться только порядком конъюнкций и расстановкой переменных в конъюнкциях. Для функции, заданной табл. 8, СДНФ имеет вид:
а для импликации (см. табл. 3)
(При написании формул булевой алгебры с конъюнкцией принято обращаться так же, как в обычной алгебре — с умножением: знак конъюнкции и скобки, ее окружающие, опускаются.)
СДНФ обычно весьма громоздкая формула. Упрощение формул в булевой алгебре (как и в любой другой алгебре) производится на основе
эквивалентных преобразований, опирающихся на основные законы (эквивалентные соотношения), которые в каждой алгебре — свои.
В булевой алгебре эти законы — следующие.
1. Ассоциативность дизъюнкции и конъюнкции:
2. Коммутативность дизъюнкции и конъюнкции:
3. Дистрибутивность конъюнкции относительно дизъюнкции:
4. Дистрибутивность дизъюнкции относительно конъюнкции:
5. Идемпотентность (отсутствие степеней и коэффициентов) :
6. Закон двойного отрицания:
7. Свойства констант 0 и 1:
8. Правила де Моргана:
9. Закон противоречия:.
10. Закон исключенного третьего:
Законы 1, 2, 3, 7 показывают, что свойства конъюнкции очень похожи на свойства умножения; поэтому ее часто называют логическим умножением. Из законов 6 и 8 следует, что, используя отрицание, дизъюнкцию можно выразить через конъюнкцию, и наоборот:
Это означает, что наборы {И, НЕ} и {ИЛИ, НЕ} также являются функционально полными.
Эквивалентные соотношения, т. е. две формулы, соединенные знаком равенства, — это утверждения о том, что данные формулы выражают одну и ту же функцию, т. е. при любых значениях, входящих в них переменных принимают равные значения. Поскольку число различных наборов значений логических переменных конечно, эквивалентные соотношения алгебры логики можно доказывать, перебрав все эти наборы (т. е. по существу построить таблицы функций для левой и правой формул и убедиться, что они совпадают). Такой способ доказательства громоздок; однако без него нельзя обойтись только при доказательстве основных законов (1 — 10). Другие соотношения, часто применяемые в преобразованиях булевых формул, проще выводить с помощью основных законов. Приведем три наиболее распространенных соотношения:
Например, соотношение (4) выводится из основных законов следующим образом (последовательно используются законы 7, 3, 7, 7):
В свою очередь, используя основные законы и соотношения (4) — (6), можно заметно упростить формулы (2) и (З):
Последняя формула является наиболее простым представлением импликации в булевой алгебре:
Другие функции двух переменных представляются в булевой алгебре следующими формулами:
Заменив в формуле (1) импликацию ее булевым представлением, получим формулу, которая легко преобразуется в формулу (7)
Наряду с булевым базисом хорошо изучен базис Жегалкина, состоящий из конъюнкции, сложения по модулю 2 и константы 1. Переход к булеву базису осуществляется по формулам
Базис может состоять из одной функции: примерами являются стрелка Пирса и штрих Шеффера. Для того чтобы доказать функциональную полноту набора функций, достаточно показать, что через них можно выразить дизъюнкцию (или конъюнкцию) и отрицание. Покажем это для штриха Шеффера. Из формул (9) следует, что
Алгебра логики лежит в основе анализа и проектирования логических схем. Логические схемы состоят из логических элементов, осуществляющих логические операции. Набор операций, осуществляемых элементами, должен быть функционально полным. Анализ логической схемы, т. е. выяснение того, какие двоичные (логические) сигналы появятся на выходах этой схемы после подачи определенных входных двоичных сигналов, сводится в конечном счете к серии логических вычислений. Проектирование и оптимизация логических схем, т. е. построение схем, реализующих заданные преобразования с как можно меньшим числом элементов, проводится с использованием эквивалентных преобразований в различных логических базисах.
Любая сколько-нибудь сложная программа для ЭВМ содержит условные переходы и связанные с ними логические условия, установление истинности которых требует вычисления логических выражений по правилам алгебры логики. Поэтому логические операции имеются практически во всех универсальных языках программирования. При этом логические значения обычно имеют отличные от 0 и 1 обозначения (например, true и false), чтобы не путать их с арифметическими.
- 032900 – Русский язык и литература;
- 032600 – История;
- 033200 – Иностранный язык;
- Пояснительная записка
- 032900 – Русский язык и литература;
- 032600 – История;
- 033200 – Иностранный язык;
- Программа курса
- Математические и логические основы информатики.
- II. Арифметические и логические основы персонального компьютера.
- III. Теория алгоритмов и формальных грамматик.
- IV. Программные средства персонального компьютера.
- Учебный план
- I лекции (20 часов)
- Методические указания к лекциям
- Лекция 1
- Лексические функции как пример математизации объектов лингвистики
- Функция как математическое понятие
- Функция в лексике
- Отличие лексической функции от числовой
- Обозначение
- «Склеенные» функции
- Типы лексических функций
- Возможности использования лексических функций
- Лекция 2-3 Алгебра высказываний. Логические функции. Законы булевой алгебры
- Лекция 4 Перевод чисел из одной позиционной системы счисления в другую. Арифметика в различных системах счисления.
- Лекция 5 Количество информации
- Лекция 6 Архитектура эвм
- 4. Алгоритм решения любой задачи представляется в виде последовательности слов, называемых командами, которые определяют наименование операции и слова информации, участвующие в операции.
- Устройство процессора
- Лекция 7 Алгоритм
- Нормальный алгоритм
- Лекция 9 Понятие операционных систем
- Приложение к лекции 1 Синтаксический граф
- Синтаксическое дерево
- Типы синтаксических деревьев
- Дерево подчинения
- Стилистическая диагностика Индивидуальный синтаксис писателя
- Перевод особенностей авторского стиля на формальный язык синтаксических деревьев
- Пушкинская, лермонтовская и гоголевская фразы — сходства и различия
- Компьютерный практикум.
- Частотный анализ в филологических исследованиях (на базе словарей)
- Работа с программой PhotoShop 6
- Создание шаблона титульного листа диплома в программе word. Лабораторная работа № 1. Изучение макрокоманд программы Word
- Общие навыки Включение компьютера
- Нажатие левой клавиши устройства «Мышь».
- Установка текстового курсора в нужную позицию
- Работа с оконным интерфейсом операционной системы Windows
- Переход на вкладку в окне.
- Работа с файловой системой операционной системы Windows 2000 Открытие окна Microsoft Word.
- Закрытие окна программы Microsoft Word
- Сохранение документа (файла) на диске.
- Создание новой папки.
- Открытие папки.
- Поиск нужной папки
- Открытие документа.
- Создание нового документа
- Копирование выделенного объекта.
- Вырезание выделенного объекта.
- Вставка скопированного (вырезанного) объекта.
- Работа с файловой системой операционной системы Windows 2003 Открытие окна программы Microsoft Word
- Закрытие окна программы Microsoft Word
- Создание новой папки.
- Открытие папки.
- Поиск нужной папки
- Открытие документа.
- Сохранение документа (файла) на диске.
- Создание нового документа
- Копирование выделенного объекта в буфер обмена.
- Вставка скопированного (вырезанного) объекта из буфера обмена.
- Работа в программе Word Форматирование текста Установка автоматического переноса слов.
- Установка параметров страницы.
- Нумерация страниц.
- Установка левой границы текста с помощью бегунка
- Установка параметров абзаца.
- Установка режима выравнивания.
- Установка размера шрифта (кегля).
- Выбор гарнитуры шрифта
- Установка типа шрифта
- Переход в режим набора текста курсивом (полужирным, с подчеркиванием).
- Отмена набора текста курсивом (полужирным, с подчеркиванием).
- Выделение текста (строки, слова, символа).
- Гашение выделения текста (строки, слова, символа).
- Изменение регистра букв текста
- Изменение настройки автотекста: «Делать первые буквы предложений прописными.»
- Маркировка и нумерация списка
- Установка уровня вложенности заголовка.
- Создание оглавления
- Вставка объектов Вставка рисунка из библиотеки рисунков.
- Перемещение объекта
- Выделение объекта иди группы объектов
- Вырезание выделенного объекта.
- Изменение размера картинки
- Вставка надписи.
- Выделение надписи.
- Заведение текста в надпись
- Изменение размера надписи
- Создание эффекта тени сзади надписи.
- Установка режимов обтекания текстом картинок.
- Установка режимов обтекания текстом объектов.
- Вставка подписи к рисункам
- Группировка объектов
- Рисование стрелок и отрезков прямых линий.
- Удаление объекта
- Изменение направления текста в надписи.
- Закрашивание фона надписи
- Работа с таблицами Вставка таблицы
- Выделение ячеек таблицы.
- Вызов редактора формул.
- Статистика Установка параметра проверки статистика удобочитаемости.
- Подсчет количества вхождений заданного фрагмента текста в документ.
- Выполнить сканирование и распознавание документов в программе Fine Reader 7.
- Лабораторная работа №2 Создание текстового документа в редакторе Microsoft Word.
- Лабораторная работа № 3 Набор филологических текстов.
- Лабораторная работа №4 Создание таблиц.
- Лабораторная работа № 5 Вставка объектов (рисунков и надписей) в текст.
- Система высшего и центрального управления в Российской империи в первой половине XIX в.
- Лабораторная работа 6. Набор математических объектов и формул.
- Лабораторная работа № 7 Анализ удобочитаемости текста. Выбор тематической и удобочитаемой литературы с помощью команд программы Microsoft Word.
- § 1. Сущность методов осуществления целостного педагогического процесса и их классификация
- Задание 3 .Выбор удобочитаемого тематического текста из сети Интернет с помощью команд программы Microsoft Word.
- Лабораторная работа № 8 Расчет простых и сложных процентов
- Основные определения.
- Задача №1:
- Задания для самостоятельной работы:
- Лабораторная работа № 9 Расчеты итоговых сумм выплат при покупках в кредит
- Основные определения.
- Лабораторная работа № 10 Частотный анализ поэтических текстов по начальной букве
- Лабораторная работа №11 Частотный анализ поэтических текстов по всем буквам.
- Лабораторная работа № 12 Частотный анализ при обработке исторических фактов и географических названий.
- Строка заголовков столбцов
- Лабораторная работа № 13 Частотный анализ в филологических исследованиях (на базе словарей)
- Лабораторная работа № 14 Создание иллюстративных материалов к уроку с помощью программы Power Point –2000 с использованием Internet ресурсов.
- Лабораторная работа №15 Работа с программой PhotoShop 6
- Лабораторная работа № 16 Обработка материалов тестовых опросов в программе excel
- Лабораторная работа № 17 Создание шаблона титульного листа диплома в программе word.