Алгебра логики

Дата добавления: 16 Сентября 2011 в 06:34
Автор: Пользователь скрыл имя
Тип работы: лекция
Скачать полностью (37.90 Кб)
Работа содержит 1 файл
Скачать  Открыть 

Документ Microsoft Office Word.docx

  —  47.32 Кб

Алгебра логики (алгебра высказываний) — раздел математической логики, в котором изучаются логические операции над высказываниями. Высказывания могут быть только истинными или ложными.

Определение

Базовыми элементами, которыми оперирует алгебра логики, являются высказывания. Высказывания строятся над множеством {B,  ,  ,  , 0, 1}, где B — непустое множество, над элементами которого определены три операции:

     отрицание (унарная операция),

     конъюнкция (бинарная),

     дизъюнкция (бинарная),

      а также константы — логический ноль и логическая единица 1.

Дизъю́нкт — пропозициональная формула, являющаяся дизъюнкцией одного или более литералов (например  ). Конъюнкт — пропозициональная формула, являющаяся конъюнкциейодного или более литералов (например  ).

Аксиомы

Логические операции

Простейшим и наиболее широко применяемым примером такой  алгебраической системы является множество B, состоящее всего из двух элементов:

    B = { Ложь, Истина }

Как правило, в математических выражениях Ложь отождествляется с логическим нулём, а Истина — с логической единицей, а операции отрицания (НЕ), конъюнкции (И) и дизъюнкции (ИЛИ) определяются в привычном нам понимании. Легко показать, что на данном множестве B можно задать четыре унарные и шестнадцать бинарных отношений и все они могут быть получены через суперпозицию трёх выбранных операций.

Опираясь на этот математический инструментарий, логика высказываний изучает высказывания и предикаты. Также вводятся дополнительные операции, такие как эквивалентность   («тогда и только тогда, когда»), импликация   («следовательно»), сложение по модулю два  («исключающее или»), штрих Шеффера стрелка Пирса   и другие.

Логика  высказываний послужила основным математическим инструментом при создании компьютеров. Она легко преобразуется в битовую логику: истинность высказывания обозначается одним битом (0 — ЛОЖЬ, 1 — ИСТИНА); тогда операция   приобретает смысл вычитания из единицы;   — немодульного сложения; & — умножения;   — равенства;   — в буквальном смысле сложения по модулю 2 (исключающее Или — XOR);   — непревосходства суммы над 1 (то есть A   B = (A + B) <= 1).

Впоследствии булева алгебра была обобщена от логики высказываний путём введения характерных для  логики высказываний аксиом. Это позволило  рассматривать, например, логику кубитов, тройственную логику (когда есть три варианта истинности высказывания: «истина», «ложь» и «не определено») и др.

Свойства логических операций

    В алгебре логики выполняются следующие  основные законы, позволяющие производить тождественные преобразования логических выражений:

ОСНОВНЫЕ  ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ

Закон Для   ИЛИ Для   И
Переместительный
Сочетательный
Распределительный
Правила де Моргана
Идемпотенции
Поглощения
Склеивания
Операция  переменной с ее инверсией
Операция  с константами
Двойного  отрицания
 

Существуют методы упрощения логической функции: например, Карта Карнометод Куайна - Мак-Класки

История

Своим существованием наука «алгебра логики» обязана  английскому математику Джорджу Булю, который исследовал логику высказываний. Первый в России курс по алгебре логики был прочитанП.С. Порецким в Казанском государственном университете.

 
 
 
 
 
 
 
 
 
 

Переключательная  схема.

    В компьютерах и других автоматических устройствах широко применяются  электрические схемы, содержащие сотни  и тысячи переключательных элементов: реле, выключателей и т.п. Разработка таких схем весьма трудоёмкое дело. Оказалось, что здесь с успехом  может быть использован аппарат  алгебры логики.

Переключательная  схема — это схематическое изображение некоторого устройства, состоящего из переключателей и соединяющих их проводников, а также из входов и выходов, на которые подаётся и с которых снимается электрический сигнал.

    Каждый  переключатель имеет  только два состояния: замкнутое и разомкнутое. Переключателю Х поставим в соответствие логическую переменную х, которая принимает значение 1 в том и только в том случае, когда переключатель Х замкнут и схема проводит ток; если же переключатель разомкнут, то х равен нулю.

    Будем считать, что два переключателя Х и   связаны таким образом, что когда Х замкнут, то   разомкнут, и наоборот. Следовательно, если переключателю Х поставлена в соответствие логическая переменная х, то переключателю   должна соответствовать переменная  .

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

    Найдем  функции проводимости F некоторых  переключательных схем:

a)   

    Схема не содержит переключателей и проводит ток всегда, следовательно F=1
     

б)   

    Схема содержит один постоянно разомкнутый контакт, следовательно F=0
     

в)   

    Схема проводит ток, когда переключатель х замкнут, и не проводит, когда х разомкнут, следовательно, F(x) = x
     

г)   

    Схема проводит ток, когда переключатель х разомкнут, и не проводит, когда х замкнут, следовательно, F(x) = 
     

д)   

    Схема проводит ток, когда оба переключателя замкнуты, следовательно, F(x) = x y
     

е)   

    Схема проводит ток, когда хотя бы один из переключателей замкнут, следовательно, F(x)=x v y; 
     

ж)   

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

    Две схемы называются равносильными, если через одну из них проходит ток тогда и только тогда, когда он проходит через другую (при одном и том же входном сигнале).

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

    Задача  нахождения среди равносильных схем наиболее простых является очень  важной. Большой вклад в ее решение  внесли российские учёные Ю.И. Журавлев, С.В. Яблонский и др.

    При рассмотрении переключательных схем возникают  две основные задачи: синтез и анализ схемы.

    СИНТЕЗ  СХЕМЫ по заданным условиям ее работы сводится к следующим трём этапам:

  1. составлению функции проводимости по таблице истинности, отражающей эти условия;
  2. упрощению этой функции;
  3. построению соответствующей схемы.

    АНАЛИЗ  СХЕМЫ сводится к

  1. определению значений её функции проводимости при всех возможных наборах входящих в эту функцию переменных.
  2. получению упрощённой формулы.
Описание работы
Алгебра логики (алгебра высказываний) — раздел математической логики, в котором изучаются логические операции над высказываниями. Высказывания могут быть только истинными или ложными
Содержание
содержание отсутствует