информатика. Глава 1, часть 2_р. 1 Кодирование текстовых и символьных данных

• Название: 1 Кодирование текстовых и символьных данных
• Анкор: информатика
• Дата: 21.05.2023
• Размер: 5.84 Mb.
• Имя файла: Глава 1, часть 2_р.doc
• Тип: Документы; #1148633
• страница: 6 из 8

1.13. Математические основы информатики

1.13.1. Алгебра высказываний (алгебра логики)

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

Высказывание — это всякое повествовательное предложение, утверждающее что-либо о чем-либо, при этом непременно истинное или ложное. Логическими значениями высказываний являются "истина" и "ложь", обозначаемые 1 и 0. Высказывания, представляющие собой одно утверждение, называются простыми или элементарными, высказывания, получающиеся из элементарных с помощью грамматических связок "не", "и", "или", "если… , то…", называются сложными. Эти названия не носят абсолютного характера, высказывания, которые в одной ситуации можно считать простыми, в другой ситуации будут сложными. В алгебре логики все высказывания рассматриваются только с точки зрения их логического значения, житейское содержание игнорируется. Каждое высказывание может быть либо истинным, либо ложным, ни одно высказывание не может быть одновременно истинным и ложным. Элементарные высказывания обозначаются строчными буквами латинского алфавита: а, b, с. Из высказываний с помощью логических связок образуются новые высказывания. Рассмотрим наиболее употребительные логические связки.

Отрицанием высказывания называется новое высказывание, которое является истинным, если высказывание ложно, и ложным, если  — истинно. Обозначается , читается "не " или "неверно, что ". Все логические значения высказывания можно описать с помощью табл. 1.13. Если  — высказывание, то  — противоположное высказывание. Тогда можно образовать , которое называется двойным отрицанием высказывания. Логические значения , очевидно, совпадают со значениями . Эта операция одноместная — в том смысле, что из одного данного простого высказывания строится новое высказывание .

Логическое умножение (конъюнкция). Конъюнкцией двух высказываний и называется новое высказывание , которое истинно только когда оба высказывания и истинны, и ложно, когда хотя бы одно из и ложно. Обозначается или , читается " и ". Таблица истинности конъюнкции дана в табл. 1.14. Из определения операции конъюнкции видно, что союз "и" в алгебре логики употребляется в том же смысле, что и в повседневной речи. Однако в алгебре логики этой связкой можно связывать любые, сколь угодно далекие по смыслу высказывания. Конъюнкцию часто называют логическим умножением.

Таблица 1.13 Таблица 1.14

1	1	1
1	0	0
0	1	0
0	0	0

1	0
0	1

Логическое сложение (дизъюнкция). Дизъюнкцией двух высказываний и называется новое высказывание, которое считается истинным, если хотя бы одно из высказываний и истинно, и ложным, если они оба ложны. Обозначается , читается " или ". Логические значения дизъюнкции описываются в табл.1.15.

Таблица 1.15 Таблица 1.16

1	1	1
1	0	1
0	1	1
0	0	0

1	1	1
1	0	0
0	1	1
0	0	1

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

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

Эквиваленция (эквивалентность, логическая эквивалентность). Эквиваленцией двух высказываний и называется новое высказывание, которое истинно, когда оба высказывания и либо одновременно истинны, либо одновременно ложны, и ложно во всех остальных случаях. Обозначается , читается "для того, чтобы , необходимо и достаточно, чтобы " или " тогда и только тогда, когда ". Эквивалентность играет значительную роль в математических доказательствах. Известно, что большое число теорем формулируется в форме необходимых и достаточных условий. Это так называемые теоремы существования. Логические значения операции эквиваленции описываются в табл. 1.17.

Таблица 1.17

1	1	1
1	0	0
0	1	0
0	0	1

С помощью логических операций над высказываниями можно строить различные новые, более сложные высказывания. Всякое сложное высказывание, которое может быть получено из элементарных высказываний с помощью логических связок, называется формулой алгебры логики. Формулы алгебры логики обозначаются большими буквами латинского алфавита , , , … Две формулы алгебры логики и называются равносильными, если они принимают одинаковые логические значения при любом наборе значений, входящих в формулы элементарных высказываний. Равносильность обозначается знаком " ≡ ".

Для любых формул , , справедливы следующие равносильности.

• 
  Основные равносильности:
  

• 
  (законы идемпотентности конъюнкции и дизъюнкции);
  

— истина;

• 
  ;
  
• 
  — ложь,
  
• 
  ;
  
• 
   (закон противоречия); (1.13.1)
  
• 
  (закон исключенного третьего);
  
• 
  (закон снятия двойного отрицания);
  
• 
  (первый закон поглощения);
  
• 
  (второй закон поглощения);
  
• 
  (первая формула расщепления);
  
• 
  (вторая формула расщепления).
  

Все эти соотношения легко проверяются по таблицам истинности.

• 
  Равносильности, выражающие одни логические операции через другие:
  

• 
  (основная формула доказательств теорем существования);
  
• 
  ;
  
• 
  ;
  
• 
  ; (1.13.2)
  
• 
  (первый закон де Моргана)⁴;
  
• 
   - (второй закон де Моргана);,
  
• 
  ;
  
• 
  .
  

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

• 
  Равносильности, выражающие основные законы алгебры логики:
  

• 
  (коммутативный закон конъюнкции);
  
• 
  (коммутативный закон дизъюнкции);
  
• 
  (ассоциативность конъюнкции); (1.13.3)
  
• 
  (ассоциативность дизъюнкции);
  
• 
  (дистрибутивность конъюнкции относительно дизъюнкции);
  
• 
  (дистрибутивность дизъюнкции относительно конъюнкции).
  

Формула называется тождественно истинной или тавтологией, если она принимает значение 1 при всех значениях входящих в нее переменных. Формула называется тождественно ложной или противоречивой, если она равна 0 при всех значениях входящих в нее переменных.

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

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

Функция задается своей истинностной таблицей 1.18.

Таблица 1.18

		…
0	0	…	0	0
1	0	…	0	0
…	…	…	…	…	…
1	1	1	1	0
1	1	1	1	1

Из этой таблицы видно, что число различных двоичных наборов длины конечно и равно .

Ясно, что тавтологии и тождественно ложные функции алгебры логики представляют собой постоянные функции, а две равносильные формулы выражают одну и ту же функцию. Каждая функция определяется таблицей истинности, состоящей из строк, то есть принимает значений (каждое 0 или 1). Общее число наборов из 0 и 1 длины равно Это число равно числу различных функций алгебры логики переменных.

Каждой формуле алгебры логики соответствует своя функция. Если формулы и эквивалентны, то соответствующие им функции равны: . Это значит, что при всех значениях переменных значения и совпадают.

Каждая булева функция может быть путем эквивалентных преобразований приведена к двум особым формам, которые называются дизъюнктивной и конъюнктивной нормальными формами. Пусть переменные булевой функции , а  — набор этих переменных. Введем обозначение: , где — параметр, равный 0 или 1. Очевидно, что Тогда функцию можно представить в виде:

, (1.13.4)

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

, (1.13.5)

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

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