Категория
Информатика
Тип
реферат
Страницы
15 стр.
Дата
20.03.2014
Формат файла
.html — Html-документ
Архив
1008607.zip — 10.37 kb
  • predstavlenie-logicheskix-funkcij-ot-bolshogo-chisla-peremennyx_1008607_1.html — 35.88 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо


Текст работы

Содержание

Введение. Функции алгебры логики.

Разложение функций по переменным. Совершенная дизъюнктивнаянормальная форма.

Выводы по первым двум темам. СКНФ.

Разрешимoстьзадач в классической теории алгоритмов.

Трудоемкость алгоритмов.

Память и время как количественная характеристика алгоритма. (применительнок машине Тьюринга и современным ЭВМ).

Трудоемкость алгоритма на примере RSA, квантовые компьютеры.

Вывод.


Введение.Функции алгебры логики

Любая формула алгебрылогики зависит от переменных высказываний x1, x2… xn, полностью определяющих значение входящих в неё простых высказываний,следовательно, её можно рассматривать как функцию этих высказываний. Такиефункции, которые как и их переменные принимают значение “0” или “1”, называют функциями алгебры логики или логическими функциями. Эти функции обозначаются f(x1… xn).

Логическая переменнаяможет принимать два значения, тогда из n-переменных можно составить N= 2nкомбинаций из “0” и “1”, которые принято называть наборами переменных, иговорят, что функция f определена намножестве наборов. Посколько функция принимает два значения, то на N наборов можно построить M= mNразличных функций.

Пример. Если n=1, то наборов N=2, а функций M=4

n=2 N=4 M=16

n=4 N=8 M=256

Элементарные функции — логические функции одной или двух переменных.

Постороим при n=1 функцию f(x).

X

 f1

f2

 f3

f4

1 1 1 1 1

Здесь f1(x)=0– константа “0”;

f2(x)= 1 –константа “1”;

f3(x)= x – функция x

f5(x)= Øx – отрицание.



Ваше мнение



CAPTCHA