Двойственность в алгебре высказываний




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

К лабораторным занятиям по дисциплине

“Дискретная математика”

 

 

Новочеркасск 2008

УДК 517.8

 

Рецензент – канд. физ – мат. наук Б. Х. Олигов

 

 

Составитель Романенко Г. Н.

 

Методические указания к лабораторным занятиям по дисциплине “Дискретная математика”/

Сост. Г.Н. Романенко; Шахтинский ин-т (филиал) ЮРГТУ (НПИ). – Новочеркасск: ЮРГТУ, 2008. –

24 с. – 50 экз.

 

 

Даны указания и приведены задания к лабораторным занятиям по дисциплине “Дискретная математика”.

Предназначены для студентов специальности 230201 (071900) “Информационные системы и технологии”.

 

УДК 517.8

© Шахтинский институт ЮРГТУ, 2008

© Романенко Г.Н., 2008

Введение

Математика является базой для рационального решения большей части инженерных задач. Современная математика развивается преимущественно в интересах решения прикладных задач. Дискретная математика – это область математических знаний, предметом рассмотрения которой являются дискретные величины, объекты и процессы. Все современные устройства обработки информации являются дискретными устройствами. Логические устройства и средства компьютерной техники оперируют с числовой информацией, представленной в дискретной форме.

В данной работе приведены задания к лабораторным работам по курсу “Дискретная математика”, даны методические указания к выполнению лабораторных работ.

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

 

Алгебра высказываний

Таблица истинности

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

 

Пример 1. Построить таблицу истинности формулы ≡ x → z, (В дальнейшем знак ► означает начало доказательства, решения примера и т. д., а знак ◄ - окончание).

► Определим порядок действий в формуле

x z.

Пользуясь определениями операций , , →, заполним таблицу 1.:

 

 

Таблица 1

Таблица истинности

x y z x x → z
           
           
           
           
           
           
           
           

Упрощение формул

Первым шагом при решении задач на упрощение формул является переход к булевым операциям с помощью формул

a → b ≡ b,

a b ≡ ab .

 

Успешное решение примера зависит от умелого, эффективного применения основных равносильностей булевой алгебры высказываний.

 

Пример 1. С помощью равносильных преобразований упростить формулу

 

≡ x → z.

►Перейдем к булевым операциям и воспользуемся основными равносильностями булевой алгебры высказываний:

≡ x → z ≡ z ≡ z ≡ y z.◄

Двойственность в алгебре высказываний

Булев принцип двойственности состоит в следующем: формула двойственная к булевой формуле получается заменой , , 0 на 1, 1 на 0 и сохранением структуры формулы.

 

Пример 1. Найти формулу, двойственную к формуле

≡ x → z.

►Воспользовавшись булевым принципом двойственности, найдем формулу (, двойственную к формуле :

 

( ≡ ( у) z.◄

 

Нормальные формы

Нормальные формы формул алгебры высказываний бывают двух типов: дизъюнктивные и конъюнктивные, в каждом из этих типов выделен класс совершенных форм. СДНФ и СКНФ можно строить по таблице истинности формулы или с помощью равносильных преобразований.

 

Пример 1. Для формулы

≡ xy z найти СДНФ и СКНФ по таблице истинности.

►Схема построения СДНФ и СКНФ по таблице истинности приведена ниже для формулы ≡ xy z:

Таблица 2

Построение СДНФ, СКНФ

x y z xy xy z
        1→
        0→x y
        1→
        0→x
        1→x
        0→
        0→
        1→xyz

 

x xyz – СДНФ

≡ (x y ) (x ) () () –СКНФ◄

 

Множества



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2019-12-28 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: