Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Представление функций формулами. Равносильные формулы.

Читайте также:
  1. А. Вспомогательные элементы для связи функций между собой
  2. Анализ, обобщение, интерпретация и представление статистических данных
  3. Анатомо-морфологическая база высших психических функций
  4. Анатомо-морфологическая база высших психических функций.
  5. Б. Представление синусоидальных величин комплексными числами.
  6. В то же время, старение тела - это прогрессирую­щий ожог химическими веществами, который приводит к повреждению желез и нарушению их функций, вплоть до их полой дисфункции.
  7. Векторное и растровое представление графической информации

Факультет Кибернетики

Кафедра Автоматизированных систем

 

 

Носырева Л.Л.

 

 

Конспективный материал к лекциям

(рабочий вариант)

 

Для специальностей АСУ, МЭИ, ИП, АСОК

 

 

Часть 5

 

 

Иркутск 2006

 

 

БУЛЕВЫ ФУНКЦИИ

Основные понятия и определения.

 

    Определение булевой функции     таблицы истинности 2 строк = Булевы функции от одной переменной Булевы функции от двух переменных Определение1. Функциюf, принимающую одно из двух значений, 0 или 1, от n переменных, каждая из которых принимает одно из двух значений, 0 или 1, называется булевой функцией f(x1,x2,…, xn) от n переменных. Иначе говоря, булевой называется функция вида: f: {0,1}→ {0,1}. Множество булевых функций от n переменных будем обозначать . Любая булева функция может быть задана в виде таблицы истинности. Если значение функции f зависит от n переменных то таблица истинности содержит 2 строк, соответствующих всем различным комбинациям значений этих переменных. Пример 1.1. Рассмотрим, например, устройство, фиксирующее принятие некоторой резолюции комитетом «трех». Каждый член комитета при одобрении резолюции нажимает свою кнопку; если большинство членов согласны, то резолюция принимается, что фиксируется регистрирующим прибором. Устройство реализует функцию f(x1, х2, х3), таблица истинности которой имеет вид таблицы1.   Таблица 1.
x1 х2 х3 f(x1, х2, х3) x1 х2 х3 f(x1, х2, х3)
               
               
               
               

 

Число булевых функций от n переменных равно числу столбцов, которые можно сопоставить строкам таблиц истинности и равно , т.е. = .

 

Булевы функции от одной переменной приведены в таблицах 2,3от двух переменных в таблицах 4,5.

Таблица 2.

x f0 f1 f 2 f 3
         
         

 

Таблица 3.

функция обозначение название
f0   Конст.0
f1 х х
f2 х, Отрицание х
f3   Конст.1

 

 

Таблица 4.

Переменные Булевы функции
x1 x2 f0 f1 f 2 f 3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15
                                   
                                   
                                   
                                   

 

Таблица 5.

функция обозначение название
f0   константа нуль.
f1 x1 х2; x1 х2 конъюнкция
f2 левая коимпликация
f3  
f4 правая коимпликация.  
f5  
f6 сложение по модулю два
f7 дизъюнкция
f8 ; функция Вебба, стрелка Пирса
f9 функция эквивалент­ности
f10 , отрицание.
f11 правая импликация
f12 , отрицание.
f13 левая импликация, импликация
f14 функция Шеффера.  
f15   константа единица.  

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

Булевы функции от одной и двух переменных являются операциями на множестве булевых функций.

 

 

Представление функций формулами. Равносильные формулы.

 

Определение формулы Определение равносильности формул Основные эквивалентности между формулами: Пусть F={f1, f2,…, fm} -множество булевых функций. Формулой над F называется выражение вида f(t1,t2,…,tn), где и ti либо переменная, либо формула над F. Всякой формуле однозначно соответствует некоторая булева функция. Зная таблицы истинности для функций множества F можно вычислить таблицу истинности той функции, которую реализует данная формула.   Пример 2.1.     Пример 2.2.         Различные формулы могут иметь одинаковые таблицы истинности, т.е. одна и та же формула может иметь множество реализаций над одним и тем же базисом. Так возникает понятие эквивалентности (равносильности) формул. Формулы и называются равносильными , если совпадают их таблицы истинности, т. е. совпадают представляемые этими формулами функции и . Пример 2.3. Построив таблицы истинности формул , убеждаемся, что  
x y
           

 

Легко видеть, что отношение ~ является отношением экви­валентности, т. е. оно рефлексивно , симметрично и транзитивно .

Основные эквивалентности между формулами:

 

       
1. , (идемпотентность );
2. (коммутативность );
3. , (ассоциативность )
4. , (дистрибутивность);
5. (законы поглощения);
6. (законы де Моргана);
7. (закон двойного отрицания);
8. ; ; законы, определяющие действия с константами 0 и 1  
9.
10.  
11.    
12.  
13.  
14.  
15.  

 

Замечание. Знак в формулах обычно опускают, т.к. конъюнкцию называют еще логическим умножением.

Формула называется выполнимой (опровержимой), если существует такой набор значений переменных, при котором формула принимает значение 1 (соответственно 0).

Пример 2.3. Формула является одновременно выполнимой и опровержимой, поскольку .

 

Формула называется тождественно истинной, общезначимой или тавтологией (тождественно ложной или противоречием), если эта формула принимает значение 1 (соот­ветственно 0) при всех наборах значений переменных, т. е. функ­ция f является константой 1 (константой 0).

Пример 2.4. Формула является тождественно истинной, а формула - тождественно ложной:

 

x
     
     

 

Если - тождественно истинная формула, то иногда пишут . В противном случае пишем .Таким образом, , и .

 

Очевидно, что:

1. формула тождественно ложна тогда и только тогда, когда тождественно истинна ();

2. формула опровержима тогда и только тогда, когда она
не является тождественна истинной ();

3. формула выполнима тогда и только тогда, когда она не является тождественно ложной.

Тождественно истинные (соответственно тожде­ственно ложные) формулы образуют класс эквивалентности по отношению ~.

 

 

 


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


Читайте в этой же книге: Дизъюнктивные и конъюнктивные нормальные формы. | Совершенные ДНФ и КНФ. | Алгоритм нахождения СДНФ функции, заданной таблицей истинности. | Минимизция булевых функций в классе ДНФ | Задача минимизция булевых функций в классе ДНФ заключается в том, чтобы для данной булевой функции f найти ДНФ, представляющую эту функцию и имеющую наименьшую сложность L(f). | Замыкание множества булевых функций. | Многочлены Жегалкина |
<== предыдущая страница | следующая страница ==>
Выводы и предложения| Принцип двойственности

mybiblioteka.su - 2015-2024 год. (0.012 сек.)