Учебная САПР электронных средств. Асланянц В.Р. - 5 стр.

      Исчисление высказываний (логика Буля)
      Формализация силлогистики (логики Аристотеля), выполненная Дж.
Булем, привела к появлению исчисления высказываний (булевой логики)
[11]. В логике Буля сложные высказывания представляются в виде ППФ –
правильно построенных формул логики.
      Дж. Булем были введены также простейшие функции алгебры логи-
ки - конъюнкция, дизъюнкция, отрицание, импликация, эквивалентность и
др. Простейшие и более сложные булевы функции описываются таблица-
ми истинности. В исчислении высказываний (одной из дедуктивных сис-
тем) к формулам (сначала к аксиомам) применяют правила вывода (прави-
ло отделения, правило резолюции и др.) и получают цепочку выводов.
      В алгебре логики действуют ряд законов, таких как переместитель-
ный, сочетательный, законы де Моргана, законы поглощения и др.
      Булевы функции могут быть представлены в дизъюнктивной (ДНФ),
конъюнктивной (КНФ) нормальной форме, в совершенной ДНФ (СНДФ)
или совершенной КНФ (СКНФ). Эти формы используются при синтезе ло-
гических схем ЭС, в том числе при программировании ПЛИС.
      Теория алгоритмов
      Интуитивное понятие алгоритма подкрепляется эмпирическими
свойствами алгоритмов:
      • дискретность;
      • детерминированность;
      • массовость;
      • результативность.
      Существуют так называемые алгоритмически неразрешимые про-
блемы (задачи), например проблема самоприменимости (парадокс брадо-
брея) и др.
      К способам представления алгоритмов относят:
      • словесное описание алгоритма;
      • схемное описание;
      • псевдокоды;
      • языки программирования.
      Наиболее важными критериями оценки и сравнения алгоритмов яв-
ляются следующие:
      • быстродействие алгоритма;
      • точность алгоритма;




                                                                     5