Существуют такие наборы логических функций, с помощью которых можно выразить любые другие логические функции. Они называются функционально полными или базисами.
Наиболее известный базис — это набор функций И, ИЛИ, НЕ. Функция штрих Шеффера является базисной, также как и функция стрелка Пирса. Поэтому, с помощью логических элементов ИЛИ-НЕ или И-НЕ можно собрать любую логическую схему. На таких элементах собран микропроцессор компьютера и другие логические устройства. Логические схемы состоят из логических элементов, осуществляющих логические операции.
Логика — наука, изучающая методы установления истинности или ложности одних высказываний на основе истинности или ложности других высказываний (утверждений). Логика изучает методы доказательств и опровержений. Логика составляет основу всякого управления, в том числе технологическими процессами.
Математическая логика — современная форма логики, опирающаяся на формальные математические методы.
Основные объекты логики — высказывания, то есть предложения, которые могут быть либо истинными, либо ложными. Существуют два подхода установления истинности высказываний: эмпирический (опытный) и логический. При эмпирическом подходе истинность высказываний устанавливается на основе наблюдений, экспериментов, документов и других фактов. При логическом подходе истинность высказываний доказывается на основе истинности других высказываний, то есть чисто формально, на основе рассуждений без обращения к фактам.
В языках программирования QBasic и Turbo Pascal логические функции И, ИЛИ, НЕ реализуются в виде логических операций OR (ИЛИ), AND (И), NOT (НЕ).
Множество всех логических функций, на котором определены три логические операции И, ИЛИ, НЕ называется булевой алгеброй (по имени основоположника математической логики английского математика Джорджа Буля). Упрощение формул в булевой алгебре производится на основе эквивалентных преобразований, опирающихся на следующие основные законы (эквивалентные соотношения):
Кроме того, применяются ещё три соотношения:
-
Законы 1,2,3,7 показывают, что свойства конъюнкции очень похожи на свойства умножения, поэтому её часто называют логическим умножением. Из законов 6 и 8 следует, что используя отрицание, дизъюнкцию можно выразить через конъюнкцию, и наоборот:
-
Это означает, что наборы И-НЕ и ИЛИ-НЕ также являются функционально полными или базисными.
-
Равносильные преобразования логических формул имеют то же назначение, что и преобразования формул в обычной алгебре. Они служат для упрощения формул или приведения их к определённому виду путем использования основных законов алгебры логики.
Под упрощением формулы понимают равносильное преобразование, приводящее к формуле, которая либо содержит по сравнению с исходной меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул, либо содержит меньшее число вхождений переменных.
Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), тогда как другие преобразования основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).
При упрощении используется закон идемпотенции; затем комбинируются два первых и два последних сомножителя и используется закон склеивания