Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Другие операции алгебры логики





Основы алгебры логики

Другие операции алгебры логики........................................................................................................................... 5

Импликация (следствие)......................................................................................................................................................... 5

Эквивалентность (равносильность)................................................................................................................................... 5

Штрих Шеффера........................................................................................................................................................................... 6

Стрелка Пирса............................................................................................................................................................................... 6

Определение значения формулы............................................................................................................................. 7

Тавтология..................................................................................................................................................................................... 7

Противоречивые или невыполнимые формулы............................................................................................................ 7

Выполнимые формулы............................................................................................................................................................. 7

Законы алгебры логики.................................................................................................................................................... 7

Порядок выполнения логических операций в сложном логическом выражении....................................... 8

Задачи.............................................................................................................................................................................................. 8

Условные обозначения логических функций на схемах................................................................ 8

Совершенные нормальные формы......................................................................................................................... 9

Переход от логической функции к логической схеме.................................................................... 10

 

Алгебра логики - система алгебраических методов решения логических задач и совокупность таких задач. Алгебра логики является основным математическим аппаратом, используемым при анализе и синтезе дискретных элементов и устройств, к каковым относятся компьютеры. Название «булева алгебра» дано в честь английского математика девятнадцатого века Джорджа Буля (Boole), который разработал алгебру логики и представил. Основные работы Дж. Буля «An investigation of law of thought …» (Исследование законов мышления»), 1854 г.

Алгебра логики — это формальный аппарат описания логики процессов в цифровых устройствах. Алгебра логики имеет дело с логическими переменными, которые могут принимать только два значения, называемые различными авторами ИСТИНА и ЛОЖЬ, TRUE и FALSE, ДА и НЕТ, 1 и 0.

Определение 1 (Функция). Пусть A и B являются множествами, функция из A в B является правилом, которое задает способ нахождения единственного bÎВ для каждого аÎА. Для обозначения функции используется запись f(a) = b и также можно сказать, что f отображает a в b. Мы также говорим, что значением f от a является b.

Также можно запись f: A → B, чтобы указать что f является функцией из A в B. Множество A называется областью определения функции, а B – областью значений функции f.

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

Определение 2 (Декартово произведение). Декартовым произведением множеств A и B называется множество А × В элементами которого являются всевозможные упорядоченные пары элементов (a, b), где аÎА и bÎВ. Т.е. А × В={(а, b) | аÎА и bÎВ}.

Определение 3. (Декартово произведение п-ой степени). Запись А × А ×... × А (п раз) тождественна записи Аn и называется декартовым произведением п-ой степени множества А. Декартово произведение также можно записать в виде {0, 1}n.

Рассмотрим особый класс функций, называемых «булевыми функциями»

Определение 4 (Булева функция). Булева функция является функцией f отображающей декартово произведение п-ой степени ×n{0, 1} в {0, 1}. Т.е. f: ×n{0, 1} →{0, 1}. Областью определения функции f является множество ×n{0, 1}, которое по определению является множеством всех n-кортежей (x1, …, xn) где каждое xi равно 0 или 1. Множество {0, 1} называется областью значений функции f.

p q r g
       
       
       
       
       
       
       
       

Пример1. (Табличное задание булевых функций). Одним из способов представления функций, чья область определения является конечной это табличное задание. Каждому элементу x области определения соответствует значение функции f(x). Далее представленные таблицы определяют булевы функции:

f: ×2{0, 1} →{0, 1}и g: ×3{0, 1} →{0, 1}.

 

p q f
     
     
     
     

 

 

Для функции f первые два значения каждой строки задают аргумент функции f, а третье значение столбца задаёт значение функции f на этом аргументе. Таким образом, f(0, 0) = 0, f(0, 1) = 1, f(1, 0) = 0, и f(1, 1) = 1.

Для функции g первые три значения каждой строки является элементом множества ×3{0, 1} (т.е. тройка (p, q, r) из 0 и 1) задают аргумент функции g, а четвертый элемент каждой строки задаёт значение функции f на этом аргументе. Таким образом, g(0, 0, 0) = 1, g(0, 0, 1) = 1, g(0, 1, 0) = 0, etc.

Следует заметить, что в примерах использовались переменные, обозначенные как p, q и r, а не x, y и z, которые обычно используются для обозначения переменных. Для обозначения переменных можно использовать любые имена, но переменные p, q и r, как правило, используются при исследовании булевых функций.

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

Пример 2. (Количество булевых функций). Сколько можно задать булевых функций с областью определения ×3{0, 1}? В более общем виде, сколько можно задать булевых функций с областью определения ×n{0, 1}?

Данная задача решается в два действия.

  1. Определить количество элементов в области определения ×n{0, 1}. Для обозначения количества элементов во множестве S будем использовать запись вида |S|, которая также называется мощность множества S. В нашем случае |×n {0, 1}| = |{0, 1}|n. построим в области определения все n-кортежи x1, x2,..., xn где xi ∈{0, 1} для i = 1, 2,..., n. Можно присвоить x1 два значения, можно присвоить два значения x2 и т.д. Это означает, что общее количество элементов в области определения 2 × 2 × ··· × 2 = 2n.
  2. Подсчитать количество булевых функций. В построении булевой функции h: ×3{0, 1} → {0, 1}, можно присвоить два различных значения функции h(p, q, r) для каждого элемента (p, q, r)∈×3{0, 1}. Как показано выше существует 23 элементов вида (p, q, r) в ×3{0, 1}. Таким образом общее количество булевых функций h: ×3{0, 1} → {0, 1} равно 2*(23). В общем количество булевых функций h: ×n{0, 1} → {0, 1} равно 2*(2n).

Пример 3. (Простейшие булевы функции). Простейшими булевыми функциями является константные функции. Поскольку есть только две константы 0 и 1, существует только две константных булевых функций.

Пример 4. (Булевы функции от одной переменной: неконстантные).

Следующими простейшими булевыми функциями являются те, которые зависят только от одной переменной, которые не являются константами. Поскольку существует 2*(21) = 22 = 4 булевых функций с одной переменной, из которых две являются константными. Т.о. существует 4 -2 = 2 неконстантных функций от одной переменной. Одну из этих функций можно определить как f(p) = p для всех p ∈ {0, 1}.

Другую функцию с одной переменной определяем как «not p». Обозначим данную функцию как n(p). Определение этой функции следующее: n(p) = 0 if p = 1, n(p) = 1 if p = 0. Чаще эту функции обозначают ∼p, реже n(p). ∼0 = 1 and ∼1 = 0. Символ “∼” называется «унарной операцией отрицание». Унарная означает, что функция имеет одну переменную. В литературе обозначается различными способами: «Øx», «не(x)»,`x

Таблица истинности отрицания следующая:

`0=1

`1=0

Пример 5. (Булевы функции от двух переменных: and, or, исключительное or). Очевидно, что существует 2^(22)= 24=16 булевых функций от двух переменных. В этом примере рассмотрим три наиболее часто используемых функции.

Первую функцию мы определим, как «p and q». Обозначим эту функцию f(p,q). По определению, f(p, q) = 1 тогда и только тогда когда значения обоих аргументов равны 1, в противном случае значение функции равно 0. Одно из наиболее употребимых обозначений данной функции p ∧ q. Тогда мы можем записать:

0 ∧ 0 = 0, 0 ∧ 1 = 0, 1 ∧ 0 = 0, 1 ∧ 1 = 1.

Бинарная функция (pÙq) также называется конъюнкцией (лат. conjunctio - союз, связь) или логическим умножением. Конъюнкция в литературе может иметь обозначения: «&», «и», «•».

Таблица истинности конъюнкции следующая:

p ∧ q    
     
     

 

Вторую функцию определим как «p or q». Обозначим эту функцию g(p,q). По определению, g(p, q) = 0 тогда и только тогда когда значения обоих аргументов равны 0, в противном случает значение функции равно 1. Одно из наиболее употребимых обозначений данной функции p ∨ q. Тогда мы можем записать:

0 ∨ 0 = 0, 0 ∨ 1 = 1, 1 ∨ 0 = 1, 1 ∨ 1 = 1.

Бинарную функцию (pÚq) также называют дизъюнкцией (лат. disjunctio - разобщение) или логическим сложением. Дизъюнкция в литературе может иметь обозначения: "+","или", «or».

Таблица истинности дизъюнкция следующая:

pÚq    
     
     

 

Третью функцию определим как «p xor q». Обозначим эту функцию h(p,q). По определению, h(p, q) = 1 тогда и только тогда когда значения только одного аргумента равно 1, в противном случае значение функции равно 0. Одно из наиболее употребимых обозначений данной функции. p ⊕ q. Тогда мы можем записать:

p ⊕ q = 0 if p = q и p ⊕ q = 1 if p ≠ q.

Таблица истинности исключительного ИЛИ следующая:

p ⊕ q    
     
     

 

Представим значения этих функций в сводной таблице:

p q f= p ∧ q   p q g=p ∨ q   p q h= p ⊕ q
                     
                     
                     
                     

 

Символы ∨, ∧, ⊕ называются «бинарными операторами» поскольку используют две переменные.

Импликация (следствие)

Бинарная булева функция импликация (от лат. implicio – тесно связываю). Импликация в литературе имеет обозначения " ".

Таблица истинности импликации следующая:

p→ q    
     
     

Штрих Шеффера

Бинарная булева функция, ложная тогда и только тогда, когда оба высказывания p и q истинны.

Штрих Шеффера в литературе имеет обозначения: «|».

Генри Шеффер (Henry Sheffer ) в 1913 г. доказал что булева алгебра может быть определена с использованием единственной первичной бинарной логической функции, которую можно выразить через отрицание и конъюнкцию

Таблица истинности штриха Шеффера следующая:

p|q    
     
     

 

Легко заметить, что штрих Шеффера – это отрицание конъюнкции или дизъюнкция отрицаний p и q. Эту операцию также называют И-НЕ.

Стрелка Пирса

Бинарная булева функция, истинная тогда и только тогда, когда оба высказывания ложны.

Стрелка Пирса в литературе имеет обозначение "↓ "..

Чарльз Пирс в 1880 году пришёл к результатам, аналогичным Г. Шефферу, но его результаты были опубликованы только в 1933 году.

Таблица истинности стрелки Пирса следующая

p↓q    
     
     

 

Очевидно, что стрелка Пирса – это отрицание дизъюнкции или конъюнкция отрицаний p и q. Эту операцию также называют ИЛИ-НЕ.

П ример 6. (Булевы функции и логика). Часто булевы переменные называют высказываниями, поскольку булевы функции можно соотнести с логикой. В логике мы рассматриваем 0 как FALSE, 1 как TRUE.

Предположим, что p обозначает высказывание «Сегодня идёт дождь», а q обозначает высказывание «Я пойду в университет». Рассмотрим основные булевы функции.

∼p соответствует “not («Сегодня идёт дождь»), что в естественном языке записывается «Сегодня не идёт дождь». В соответствии с определением функции ∼ если p является истинным, то ∼p – ложным.

p ∧ q соответствует высказыванию «Сегодня идёт дождь и я пойду в университет»

p ∨ q соответствует высказыванию, «завтра у меня занятия или я остаюсь дома».

p ⊕ q соответствует высказыванию “Either I have classes tomorrow or I will stay home

Бинарная булева функция импликация (от лат. implicio – тесно связываю), приблизительный логический эквивалент оборота «если…то …».

p→ q соответствует

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

1. отрицание (самая старшая операция)

2. конъюнкция

3. дизъюнкция

Тавтология

Формулы алгебры логики, которые при всех наборах значений переменных принимают значения «1», называются тавтологиями.

Выполнимые формулы

Формулы алгебры логики, которые не некоторых наборах значений переменных принимают значения «0», а при других значений переменных принимают значений значения «1», называются выполнимыми.

Законы алгебры логики

операции с «0»

операции с «1»

коммутативный (переместительный)

ассоциативный (сочетательный)

дистрибутивный (распределительный)

законы поглощения

законы идемпотентности

законы де Моргана

Задачи

1. Привести таблицу истинности для штриха Шеффера. Выразить штрих Шеффера через отрицание и конъюнкцию. Выразить отрицание через штрих Шеффера.

2. Привести таблицу истинности для стрелки Пирса. Выразить стрелку Пирс через отрицание и дизъюнкцию. Выразить отрицание через стрелку Пирса.

3. Привести таблицу истинности для исключительное ИЛИ. Выразить исключительное ИЛИ через отрицание и эквивалентность.

Основы алгебры логики

Другие операции алгебры логики........................................................................................................................... 5

Импликация (следствие)......................................................................................................................................................... 5

Эквивалентность (равносильность)................................................................................................................................... 5

Штрих Шеффера........................................................................................................................................................................... 6

Стрелка Пирса............................................................................................................................................................................... 6

Определение значения формулы............................................................................................................................. 7

Тавтология..................................................................................................................................................................................... 7

Противоречивые или невыполнимые формулы............................................................................................................ 7

Выполнимые формулы............................................................................................................................................................. 7

Законы алгебры логики.................................................................................................................................................... 7

Порядок выполнения логических операций в сложном логическом выражении....................................... 8

Задачи.............................................................................................................................................................................................. 8

Условные обозначения логических функций на схемах................................................................ 8

Совершенные нормальные формы......................................................................................................................... 9

Переход от логической функции к логической схеме.................................................................... 10

 

Алгебра логики - система алгебраических методов решения логических задач и совокупность таких задач. Алгебра логики является основным математическим аппаратом, используемым при анализе и синтезе дискретных элементов и устройств, к каковым относятся компьютеры. Название «булева алгебра» дано в честь английского математика девятнадцатого века Джорджа Буля (Boole), который разработал алгебру логики и представил. Основные работы Дж. Буля «An investigation of law of thought …» (Исследование законов мышления»), 1854 г.

Алгебра логики — это формальный аппарат описания логики процессов в цифровых устройствах. Алгебра логики имеет дело с логическими переменными, которые могут принимать только два значения, называемые различными авторами ИСТИНА и ЛОЖЬ, TRUE и FALSE, ДА и НЕТ, 1 и 0.

Определение 1 (Функция). Пусть A и B являются множествами, функция из A в B является правилом, которое задает способ нахождения единственного bÎВ для каждого аÎА. Для обозначения функции используется запись f(a) = b и также можно сказать, что f отображает a в b. Мы также говорим, что значением f от a является b.

Также можно запись f: A → B, чтобы указать что f является функцией из A в B. Множество A называется областью определения функции, а B – областью значений функции f.

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

Определение 2 (Декартово произведение). Декартовым произведением множеств A и B называется множество А × В элементами которого являются всевозможные упорядоченные пары элементов (a, b), где аÎА и bÎВ. Т.е. А × В={(а, b) | аÎА и bÎВ}.

Определение 3. (Декартово произведение п-ой степени). Запись А × А ×... × А (п раз) тождественна записи Аn и называется декартовым произведением п-ой степени множества А. Декартово произведение также можно записать в виде {0, 1}n.

Рассмотрим особый класс функций, называемых «булевыми функциями»

Определение 4 (Булева функция). Булева функция является функцией f отображающей декартово произведение п-ой степени ×n{0, 1} в {0, 1}. Т.е. f: ×n{0, 1} →{0, 1}. Областью определения функции f является множество ×n{0, 1}, которое по определению является множеством всех n-кортежей (x1, …, xn) где каждое xi равно 0 или 1. Множество {0, 1} называется областью значений функции f.

p q r g
       
       
       
       
       
       
       
       

Пример1. (Табличное задание булевых функций). Одним из способов представления функций, чья область определения является конечной это табличное задание. Каждому элементу x области определения соответствует значение функции f(x). Далее представленные таблицы определяют булевы функции:

f: ×2{0, 1} →{0, 1}и g: ×3{0, 1} →{0, 1}.

 

p q f
     
     
     
     

 

 

Для функции f первые два значения каждой строки задают аргумент функции f, а третье значение столбца задаёт значение функции f на этом аргументе. Таким образом, f(0, 0) = 0, f(0, 1) = 1, f(1, 0) = 0, и f(1, 1) = 1.

Для функции g первые три значения каждой строки является элементом множества ×3{0, 1} (т.е. тройка (p, q, r) из 0 и 1) задают аргумент функции g, а четвертый элемент каждой строки задаёт значение функции f на этом аргументе. Таким образом, g(0, 0, 0) = 1, g(0, 0, 1) = 1, g(0, 1, 0) = 0, etc.

Следует заметить, что в примерах использовались переменные, обозначенные как p, q и r, а не x, y и z, которые обычно используются для обозначения переменных. Для обозначения переменных можно использовать любые имена, но переменные p, q и r, как правило, используются при исследовании булевых функций.

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

Пример 2. (Количество булевых функций). Сколько можно задать булевых функций с областью определения ×3{0, 1}? В более общем виде, сколько можно задать булевых функций с областью определения ×n{0, 1}?

Данная задача решается в два действия.

  1. Определить количество элементов в области определения ×n{0, 1}. Для обозначения количества элементов во множестве S будем использовать запись вида |S|, которая также называется мощность множества S. В нашем случае |×n {0, 1}| = |{0, 1}|n. построим в области определения все n-кортежи x1, x2,..., xn где xi ∈{0, 1} для i = 1, 2,..., n. Можно присвоить x1 два значения, можно присвоить два значения x2 и т.д. Это означает, что общее количество элементов в области определения 2 × 2 × ··· × 2 = 2n.
  2. Подсчитать количество булевых функций. В построении булевой функции h: ×3{0, 1} → {0, 1}, можно присвоить два различных значения функции h(p, q, r) для каждого элемента (p, q, r)∈×3{0, 1}. Как показано выше существует 23 элементов вида (p, q, r) в ×3{0, 1}. Таким образом общее количество булевых функций h: ×3{0, 1} → {0, 1} равно 2*(23). В общем количество булевых функций h: ×n{0, 1} → {0, 1} равно 2*(2n).

Пример 3. (Простейшие булевы функции). Простейшими булевыми функциями является константные функции. Поскольку есть только две константы 0 и 1, существует только две константных булевых функций.

Пример 4. (Булевы функции от одной переменной: неконстантные).

Следующими простейшими булевыми функциями являются те, которые зависят только от одной переменной, которые не являются константами. Поскольку существует 2*(21) = 22 = 4 булевых функций с одной переменной, из которых две являются константными. Т.о. существует 4 -2 = 2 неконстантных функций от одной переменной. Одну из этих функций можно определить как f(p) = p для всех p ∈ {0, 1}.

Другую функцию с одной переменной определяем как «not p». Обозначим данную функцию как n(p). Определение этой функции следующее: n(p) = 0 if p = 1, n(p) = 1 if p = 0. Чаще эту функции обозначают ∼p, реже n(p). ∼0 = 1 and ∼1 = 0. Символ “∼” называется «унарной операцией отрицание». Унарная означает, что функция имеет одну переменную. В литературе обозначается различными способами: «Øx», «не(x)»,`x

Таблица истинности отрицания следующая:

`0=1

`1=0

Пример 5. (Булевы функции от двух переменных: and, or, исключительное or). Очевидно, что существует 2^(22)= 24=16 булевых функций от двух переменных. В этом примере рассмотрим три наиболее часто используемых функции.

Первую функцию мы определим, как «p and q». Обозначим эту функцию f(p,q). По определению, f(p, q) = 1 тогда и только тогда когда значения обоих аргументов равны 1, в противном случае значение функции равно 0. Одно из наиболее употребимых обозначений данной функции p ∧ q. Тогда мы можем записать:

0 ∧ 0 = 0, 0 ∧ 1 = 0, 1 ∧ 0 = 0, 1 ∧ 1 = 1.

Бинарная функция (pÙq) также называется конъюнкцией (лат. conjunctio - союз, связь) или логическим умножением. Конъюнкция в литературе может иметь обозначения: «&», «и», «•».

Таблица истинности конъюнкции следующая:

p ∧ q    
     
     

 

Вторую функцию определим как «p or q». Обозначим эту функцию g(p,q). По определению, g(p, q) = 0 тогда и только тогда когда значения обоих аргументов равны 0, в противном случает значение функции равно 1. Одно из наиболее употребимых обозначений данной функции p ∨ q. Тогда мы можем записать:

0 ∨ 0 = 0, 0 ∨ 1 = 1, 1 ∨ 0 = 1, 1 ∨ 1 = 1.

Бинарную функцию (pÚq) также называют дизъюнкцией (лат. disjunctio - разобщение) или логическим сложением. Дизъюнкция в литературе может иметь обозначения: "+","или", «or».

Таблица истинности дизъюнкция следующая:

pÚq    
     
     

 

Третью функцию определим как «p xor q». Обозначим эту функцию h(p,q). По определению, h(p, q) = 1 тогда и только тогда когда значения только одного аргумента равно 1, в противном случае значение функции равно 0. Одно из наиболее употребимых обозначений данной функции. p ⊕ q. Тогда мы можем записать:

p ⊕ q = 0 if p = q и p ⊕ q = 1 if p ≠ q.

Таблица истинности исключительного ИЛИ следующая:

p ⊕ q    
     
     

 

Представим значения этих функций в сводной таблице:

p q f= p ∧ q   p q g=p ∨ q   p q h= p ⊕ q
                     
                     
                     
                     

 

Символы ∨, ∧, ⊕ называются «бинарными операторами» поскольку используют две переменные.

Другие операции алгебры логики

Импликация (следствие)

Бинарная булева функция импликация (от лат. implicio – тесно связываю). Импликация в литературе имеет обозначения " ".

Таблица истинности импликации следующая:

p→ q    
     
     






Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...





Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2024 zdamsam.ru Размещенные материалы защищены законодательством РФ.