Четверг, 20.07.2017, 15:41
План-конспекты уроков по информатике
0+ Главная Регистрация Вход
Приветствую Вас, Гость · RSS
Меню сайта
Категории раздела
Все [56]
logoWriter [19]
Уроки по теме "logoWriter"
CorelDraw [7]
Практические задания с пошаговым алгоритмом выполнения по теме "CorelDraw"
MacromediaFlash [0]
Практические работы по теме "MacromediaFlash"
MS Excel [7]
План-конспекты по теме "MS Excel"
Логика [10]
План-конспекты уроков по логике
Разное [10]
Уроки, которые не подходят ни в одну категорию
Pascal [7]
Форма входа
Статистика

Яндекс.Метрика

Онлайн всего: 1
Гостей: 1
Пользователей: 0
Наш опрос
Очень сложно найти конспект на тему...
Всего ответов: 632
Реклама
 Каталог статей
Главная » Уроки » Все

Тема 11. Канонические формы логических формул

Тема 11. Канонические формы логических формул.


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

Каноническая форма- форма, построенная по какому либо правилу, закону-канону.

Логической (булевой) функцией называют функцию F(х1,х2,х3,..Хn), аргументы которой и сама функция принимают значения 0 или 1.
Логические функции могут быть заданы табличным способом или аналитическим – в виде соответствующих формул.

Элементарная конъюнкция-конъюнкция конечного множества логических переменных и их инверсий.
Элементарная дизъюнкция- дизъюнкция конечного множества логических переменных и их инверсий. 

Число аргументов, образующих элементарную конъюнкцию или дизъюнкцию, называют ее рангом.
Пример1.
X&Y&Z, X&Y&Z  - элементарные конъюнкции третьего ранга.

Дизъюнктивная нормальная форма (ДНФ)-– содержит элементарные конъюнкции, связанные между собой операцией дизъюнкции.

Конъюнктивная нормальная форма (КНФ)- содержит элементарные дизъюнкции, связанные между собой операцией конъюнкции.

    Одну и ту же логическую функцию можно представить разными ДНФ и КНФ.

Совершенная дизъюнктивная нормальная форма (СДНФ) отвечает следующим требованиям:
1) в ней нет двух одинаковых элементарных конъюнкций;
2) ни одна элементарная конъюнкция не содержит двух одинаковых переменных;
3) ни одна элементарная конъюнкция не содержит переменной вместе с ее инверсией
4) все конъюнкции имеют один и тот же набор переменных.

Совершенная конъюнктивная нормальная форма (СКНФ) отвечает следующим требованиям:
1) в ней нет двух одинаковых элементарных дизъюнкций
2) ни одна элементарная дизъюнкция не содержит двух одинаковых переменных
3) ни одна элементарная дизъюнкция не содержит переменной вместе с ее инверсией
4) все дизъюнкции имеют один и тот же набор переменных.

Пример 2
X1&X2 v X1&X2   - СДНФ –X1 X2+X1 X2
X1v X2&X3- не СДНФ
X1&X2 v X2& X2 – не СДНФ
(X1 v X2 ) & (X1 v X2)- СКНФ
(X1 v X1) & (X2 v X3) –не СКНФ

Теорема 1. Пусть F(х1,х2,х3,..Хn)-булева функция  от n переменных, не равная тождественно нулю. Тогда существует СДНФ, выражающая функцию F.
Теорема 2. Пусть F(х1,х2,х3,..Хn)-булева функция  от n переменных, не равная тождественно единице. Тогда существует СКНФ, выражающая функцию F.

 СДНФ и СКНФ можно получить по таблице истинности логической функции.

Алгоритм построения СДНФ по таблице истинности

1) выделить в таблице все наборы переменных, на которых функция принимает единичные значения.
2) Для каждого  выбранного набора  записать  конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае – ее отрицание.
3) все полученные элементарные конъюнкции соединить знаком дизъюнкции.
Алгоритм построения СКНФ по таблице истинности
1) выделить в таблице все наборы переменных, на которых функция принимает нулевые значения.
2) Для каждого  выбранного набора  записать  дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 0, то в дизъюнкцию включаем саму переменную, в противном случае – ее отрицание.
3) все полученные элементарные дизъюнкции соединить знаком конъюнкции.

Пример 3 Пусть функция F(x1,x2,x3) задана таблицей истинности. Используя описанный алгоритм построим для нее СДНФ.
X1    X2    X3    F
0    0    0    0
0    0    1    0
0    1    0    1
0    1    1    0
1    0    0    1
1    0    1    1
1    1    0    0
1    1    1    0
 Ответ:  (x1 & x2 & x3) v ( x1 & x2 & x3) v  (x1&x2&x3)
Задания: 1.По заданным таблицам истинности дайте аналитическое представление 
1)    импликации
2)    эквивалентности
3)    строгой дизъюнкции
2. По таблице истинности записать СДНФ и СКНФ для F1 и F2.

x    y    z    F1    F2
0    0    0    0    0
0    0    1    0    1
0    1    0    1    0
0    1    1    1    1
1    0    0    0    0
1    0    1    1    0
1    1    0    0    1
1    1    1    1    1

Категория: Все | Добавил: Казначей (07.12.2015)
Просмотров: 1868 | Теги: Канонические формы логических форму, скнф, сднф | Рейтинг: 0.0/0
Не забываем комментировать!!!

Другие материалы
Цикл с постусловием (цикл "ДО")
Урок 8: Работа с листом форм в среде LogoWriter
Арифметика в двоичной системе счисления.
Графика в Турбо Паскаль.
Урок 10: Работа с листом форм в среде LogoWriter
Урок 3: Команды перемещения исполнителя черепашка
Урок 2: Команды перемещения исполнителя черепашка
Урок 12. Команда ПОВТОРИ. Изображение правильных м...
Урок 7: Построение изображений в цвете
Урок 18, 19. Понятие переменной. Вычисление значен...
Практическая работа №7: Визитная карточка
Магистрально-модульный принцип построения компьюте...

Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Copyright KUPI © 2017
Готовимся к ЕГЭ и ГИА
ГИА, ЕГЭ 2014 по информатике ФИПИ скачать бесплатно без смс
Отследи свою посылку
Друзья сайта
  • Софт бесплатно
  • Интернет магазин бесплатно
  • Наша ссылка
    Наша кнопка
    Конспекты уроков
    Лидеры по просмотрам
    Тема 8. Решение логических задач.
    Виды и типы современных языков программирования
    Алгоритм и его свойства
    Информация: определение, свойства, формы представления; информационные процессы.
    Тема 7. Перевод и запись различных выражений с естественного языка на язык алгебры логики.
    Относительная и абсолютная адресация
    Моделирование и формализация. Часть 1.
    Графика в Турбо Паскаль.
    Сортировка и фильтрация данных в MS Excel
    Понятие формализации. Часть 2.
    Загрузить файл
    Сделать бесплатный сайт с uCoz