Xreferat.com » Рефераты по информатике и программированию » Основы дискретной математики

Основы дискретной математики

'10101'); Form1. StringGrid1. Cells [k, 0]:='Х'; end;

if ('Ц' in T) then begin S. Lines. Add ('Ц = '+' 10110'); inc(k); SNDF (k, '10110'); Form1. StringGrid1. Cells [k, 0]:='Ц'; end;

if ('Ч' in T) then begin S. Lines. Add ('Ч = '+' 10111'); inc(k); SNDF (k, '10111'); Form1. StringGrid1. Cells [k, 0]:='Ч'; end;

if ('Ш' in T) then begin S. Lines. Add ('Ш = '+' 11000'); inc(k); SNDF (k, '11000'); Form1. StringGrid1. Cells [k, 0]:='Ш'; end;

if ('Щ' in T) then begin S. Lines. Add ('Щ = '+' 11001'); inc(k); SNDF (k, '11001'); Form1. StringGrid1. Cells [k, 0]:='Щ'; end;

if ('Ъ' in T) then begin S. Lines. Add ('Ъ = '+' 11010'); inc(k); SNDF (k, '11010'); Form1. StringGrid1. Cells [k, 0]:='Ъ'; end;

if ('Ы' in T) then begin S. Lines. Add ('Ы = '+' 11011'); inc(k); SNDF (k, '11011'); Form1. StringGrid1. Cells [k, 0]:='Ы'; end;

if ('Ь' in T) then begin S. Lines. Add ('Ь = '+' 11100'); inc(k); SNDF (k, '11100'); Form1. StringGrid1. Cells [k, 0]:='Ь'; end;

if ('Э' in T) then begin S. Lines. Add ('Э = '+' 11101'); inc(k); SNDF (k, '11101'); Form1. StringGrid1. Cells [k, 0]:='Э'; end;

if ('Ю' in T) then begin S. Lines. Add ('Ю = '+' 11110'); inc(k); SNDF (k, '11110'); Form1. StringGrid1. Cells [k, 0]:='Ю'; end;

if ('Я' in T) then begin S. Lines. Add ('Я = '+' 11111'); inc(k); SNDF (k, '11111'); Form1. StringGrid1. Cells [k, 0]:='Я'; end;

end;

procedure TForm1. BitBtn1Click (Sender: TObject);

var F, I, O:R;

h, j, S:byte;

begin

Memo1. Clear;

Memo2. Clear;

Memo3. Clear;

k:=0;

S:=0;

F:=['Я', 'К', 'У', 'Х', 'И', 'Н'];

I:=['Д', 'М', 'И', 'Т', 'Р'];

O:=['Е', 'Р', 'Г', 'В', 'И'];

perebor (F, Memo1);

perebor (I, Memo2);

perebor (O, Memo3);

for j:=1 to 5 do begin

for h:=1 to 19 do begin

if StringGrid1. Cells [h, j]='1' then inc(s);

end;

StringGrid1. Cells [17, j]:=IntToStr(S);

S:=0;

(yegorov-p Rulezzz;)}

end;

end;

procedure TForm1. FormCreate (Sender: TObject);

var

g:byte;

begin

StringGrid1. Cells [0,2]:='F1';

StringGrid1. Cells [0,3]:='F2';

StringGrid1. Cells [0,4]:='F3';

StringGrid2. Cells [1,0]:='X1';

StringGrid2. Cells [2,0]:='X2';

StringGrid2. Cells [3,0]:='X3';

StringGrid2. Cells [4,0]:='X4';

StringGrid2. Cells [5,0]:='F1';

StringGrid2. Cells [6,0]:='F2';

StringGrid2. Cells [7,0]:='F3';

for g:=0 to 15 do

StringGrid2. Cells [0, g+1]:=IntToStr(g);

for g:=0 to 7 do

StringGrid2. Cells [1, g+1]:='0';

for g:=8 to 15 do

StringGrid2. Cells [1, g+1]:='1';

for g:=0 to 3 do

StringGrid2. Cells [2, g+1]:='0';

for g:=4 to 7 do

StringGrid2. Cells [2, g+1]:='1';

for g:=8 to 11 do

StringGrid2. Cells [2, g+1]:='0';

for g:=12 to 15 do

StringGrid2. Cells [2, g+1]:='1';

for g:=1 to 2 do begin

StringGrid2. Cells [3, g]:='0';

StringGrid2. Cells [3, g+2]:='1';

StringGrid2. Cells [3, g+4]:='0';

StringGrid2. Cells [3, g+6]:='1';

StringGrid2. Cells [3, g+8]:='0';

StringGrid2. Cells [3, g+10]:='1';

StringGrid2. Cells [3, g+12]:='0';

StringGrid2. Cells [3, g+14]:='1';

end;

for g:=1 to 16 do begin

if g div 2 = g/2 then

StringGrid2. Cells [4, g]:='1'

else

StringGrid2. Cells [4, g]:='0';

end;

end;

Function Dec2Bin (j:integer):string;

begin

result:='';

while j>=1 do

begin

result:=IntToStr (j mod 2)+result;

j:=j div 2;

end;

end;

Function Dec2BinDrob (j:real):string;

var

i:byte;

begin

result:='';

for i:=1 to 11 do

begin

result:=FloatToStr (int(j*2))+result;

j:=j*2;

if int (j*2)>1 then j:=j 1;

end;

end;

procedure TForm1. BitBtn3Click (Sender: TObject);

var p, p2, S, S2, S3:string;

i:byte;

begin

p:=Edit1. Text;

p2:='0,'+Edit3. Text;

S:=Dec2Bin (StrToInt(p));

S2:=Dec2BinDrob (StrToFloat(p2));

for i:=11 downto 1 do begin

S3:=S3+S2 [i];

end;

Edit2. Text:=S+'.'+S3;

end;

procedure TForm1. BitBtn4Click (Sender: TObject);

var i:byte;

P:string;

begin

for i:=1 to 16 do begin

if StringGrid2. Cells [5, i]='1' then begin

P:=StringGrid2. Cells [1, i]+StringGrid2. Cells [2, i]+

StringGrid2. Cells [3, i]+StringGrid2. Cells [4, i];

Label7. Caption:=Label7. Caption+' '+P;

end;

end;

for i:=1 to 16 do begin

if StringGrid2. Cells [6, i]='1' then begin

P:=StringGrid2. Cells [1, i]+StringGrid2. Cells [2, i]+

StringGrid2. Cells [3, i]+StringGrid2. Cells [4, i];

Label8. Caption:=Label8. Caption+' ' +P;

end;

end;

for i:=1 to 16 do begin

if StringGrid2. Cells [7, i]='1' then begin

P:=StringGrid2. Cells [1, i]+StringGrid2. Cells [2, i]+

StringGrid2. Cells [3, i]+StringGrid2. Cells [4, i];

Label9. Caption:=Label9. Caption+' '+P;

end;

end;

end;

end.


Основы дискретной математики

Рисунок 4.3 – Форма для примера 2


4.4 Вопросы для самопроверки


1) Чем отличается кортеж от обычного множества?

2) Приведите пример использования кортежей в программировании.

3. Какие операции над множествами Вы знаете?

4) Какой способ существует для графического изображения множеств?

5) Приведите пример универсального множества, которое используется в данной практической работе.

6) Какие операции (логические связки) из алгебры логики Вы знаете?

7) Возможно ли провести аналогию между операциями над множествами и логическими операциями?

8) Какое правило используется при построении СДНФ логической функции?

9) Какое правило используется при построении СКНФ логической функции?

10) Каков алгоритм перевода числа из десятичной системы счисления в двоичную систему счисления?

11) Почему логические функции и логические переменные часто называют двоичными?

12) Какая связь существует между логическими функциями и функционированием компьютера, отдельных его устройств?


Практическая работа № 5. Исследование логических функций


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

Примечание: все теоретические сведения, необходимые для выполнения данной работы, содержатся в [25], в лекциях и в материалах семинарских занятий.


5.1 Задание к работе


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

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

3. Представить заданные логические функции в виде СДНФ, СКНФ и СПНФ.

4. Построить логические функциональные схемы для заданных логических функций F1 и F2.

5. Сделать выводы.


5.2 Практическая часть


5.2.1 Пример выполнения

Задание: Построить таблицу истинности, СДНФ, СКНФ, СПНФ и логические функциональные схемы для данных логических функций:


F1=Основы дискретной математики

F2=Основы дискретной математикиОсновы дискретной математики


Код программы построения таблицы истинности логический функций:

Procedure TForml. ButtonlClick (Sender: TObject);

var xl, x2, x3:boolean; i:byte;

a1, a2, a3: string;

begin

Stringgridl. Cells [l, 0]:='xl';

Stringgridl. Cells [2,0]:='x2';

Stringgridl. Cells [3,0]:='x3';

Stringgrid1. Cells [4,0]:=F1';

Stringgridl. Cells [5,0]:='F2';

for i:=l to 8 do begin Stringgrid1. Cells [0, i]:=inttostr (i 1);

if i<=4 then Stringgridl. Cells [l, i]:=’0’ else Stringgridl. Cells [l, i]:=1;

if (i<=2) or (i=5) or (i=6) then Stringgridl. Cells [2, i]:='0’ else Stringgridl. Cells [2, i]:=' 1';

if (i mod 2 >0) then Stringgridl. Cells [3, i]:='0' else Stringgridl. Cells [3, i]:=1; end;

for i:=l to 8 do begin

x1:=strtobool (Stringgrid 1. Cells [1, i]);

x2:=strtobool (Stringgridl. Cells [2, i]);

x3:=strtobool (Stringgridl. Cells [3, i]);

if (x2 and x3) or (not(xl) and not(x2)) or (x3 and not(xl)) then

Stringgridl. Cells [4, i]:=’1’ else Stringgridl. Cells [4, i]:='0';

if (x2 and x3) or (not(xl) and not(x2) and not(x3)) then Stringgridl. Cells [5, i]:=1 else Stringgridl. Cells [5, i]:='0'; end; end;


Основы дискретной математики

Рисунок 5.1 – Форма с результатами


МДНФ:

F1 = Основы дискретной математики

F2 = Основы дискретной математики

МКНФ:

F1 = Основы дискретной математики

F2 = Основы дискретной математики

СПНФ:

F1 =Основы дискретной математики

F2 =Основы дискретной математики


Основы дискретной математики

Рисунок 5.2 – Логическая схема для МКНФ функции F1


5.2.2 Варианты заданий

Заданы логические функции: F1= 1 на наборах 0, 3 и Основы дискретной математики

Заданы логические функции: F1= 1 на наборах 0, 1, 3 и Основы дискретной математики

Заданы логические функции: F1= 1 на наборах 3, 7 и Основы дискретной математики

Заданы логические функции: F1= 1 на наборах 0, 1, 3, 7 и Основы дискретной математики

Заданы логические функции: F1= 1 на наборах 0,1,2,3,7 и Основы дискретной математики

Заданы логические функции: F1= 1 на наборах 2,5,6 и Основы дискретной математики

Заданы логические функции: F1= 1 на наборах 0, 2,5,7 и Основы дискретной математики

Заданы логические функции: F1= 1 на наборах 0, 1,3 и Основы дискретной математики

Заданы логические функции: F1= 1 на наборах 3,4,6,7 и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и

Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики

Заданы логические функции: F1=1 на наборах 4,5,7 и Основы дискретной математики

Заданы логические функции: F1=0 на наборах 2,4 и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики

Заданы логические функции: Основы дискретной математики и Основы дискретной математики


5.3 Вопросы для самопроверки


1) Какие формы представления логических функций Вы знаете?

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

3) Изобразите общую схему таблицы истинности функции 4 х переменных.

4) Каков приоритет выполнения логических операций?

5) Какие логические функции есть в алгоритмическом языке Object Pascal?

6) Дайте определение логической функции многих переменных.

7) Приведите пример тождественно ложной логической функции. Можно ли для этой функции построить СДНФ?

8) Приведите пример тождественно истинной логической функции. Можно ли для этой функции построить СКНФ?

9) На основании каких замен можно построить арифметическую модель логической функции?

10) Перечислите законы алгебры логики.

11) Какие следствия из законов алгебры логики Вы знаете?

12) Назовите учёных, которые считаются основателями алгебры логики.



Практическая работа № 6. Изучение методов минимизации логических функций


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


6.1 Краткие теоретические сведения


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

F 0={Ч;Ъ; – ;Е;«;®;Ѕ;Ї} – сигнатура алгебры логики;

F 1={Ч;Ъ;–} – базис Буля;

F 2={Ч;–} – базис конъюнктивный;

F 3={Ъ;–} – базис дизъюнктивный;

F 4={Ч;Е; 1} – базис Жегалкина;

F 5={Ї} – базис Вебба;

F 6={Ѕ} – базис Шеффера;

F 7={®;–} – базис импликативный и т. д.

В таблицах 6.1–4 приведены формулы в некоторых базисах и для некоторых значений функции f (x1, x2).


Таблица 6.1 – Формулы, описывающие функции в базисах F0 и F5

fi Формулы в базисах F 0 и F 5
f1 (x1Чx2)=(x1Їx2)Ї(x1Їx2)
f6 (x1Еx2)=[(x1Їx1)Ї(x2Їx2)]Ї(x1Їx2)
f7 (x1Ъx2)=(x1Їx2)Ї(x1Їx2)
f9 (x1«x2)=[x1Ї(x2Їx2)]Ї[x2Ї(x1Їx1)]
f13 (x1®x2)=[x2Ї(x1Їx1)]Ї[x2Ї(x1Їx1)]
f14 (x1чx2)=[(x1Їx1)Ї(x2Їx2)]Ї [(x1Їx1)Ї(x2Їx2)]

Таблица 6.2 – Формулы, описывающие функции в базисах F0 и F2

Fi Формулы в базисах F 0 и F2
f6 (x1Еx2)=щ(`x1Ч`x2)Чщ(x1Чx2)
f7 (x1Ъx2)=щ(`x1Ч`x2)
f8 (x1Їx2)=(`x1Ч`x2)
f9 (x1«x2)=щ(x1Ч`x2)Чщ(`x1Чx2)
f13 (x1®x2)=щ(x1Ч`x2)
f14 (x1чx2)=щ(x1Чx2)

Таблица 6.3 – Формулы, описывающие функции в базисах F0 и F3

Fi Формулы в базисах F 0 и F3
f6 (x1Чx2)=щ(`x1Ъ`x2)
f7 (x1Еx2)=щ(`x1Ъx2)Ъщ(x1Ъ`x2)
f8 (x1Їx2)=щ(x1Ъx2)
f9 (x1«x2)=(x1Ъx2)Ъщ(`x1Ъ`x2)
f13 (x1®x2)=(`x1Ъx2)
f14 (x1Ѕx2)=(`x1Ъ`x2)

Таблица 6.4 – Формулы, описывающие функции в базисах F0 и F6

Fi Формулы в базисах F 0 и F 6
f1 (x1Чx2)=(x1Ѕx2)Ѕ(x1Ѕx2)
f6 (x1Еx2)=[x1Ѕ(x2Ѕx2)]Ѕ[x2Ѕ (x1Ѕx1)]
f7 (x1Ъx2)=(x1Ѕx2)Ѕ(x1Ѕx2)
f8 (x1Їx2)=[(x1Ѕx1)Ѕ(x2Ѕx2)Ѕ (x2Ѕx2)]
f9 (x1«x2)=[(x1Ѕx1)Ѕ(x2Ѕx2)]Ѕ (x1Ѕx2)]
f13 (x1®x2)=(x1Ѕ(x2Ѕx2).

6.2 Практическая часть


6.2.1 Задание к работе

1. Минимизировать функции с помощью карт Карно или таблицы Куайна.

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

3. Сделать выводы.


6.2.2 Примеры выполнения

Пример 1.

Задание:

1. Минимизировать функции с помощью таблицы Куайна.

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

1 Минимизация с помощью таблицы Куайна:

Пусть функция F представлена в виде СДНФ

F1СДНФ = Основы дискретной математики


Таблица 6.5 – таблица Куайна

х1x2x3 001 101 110 111

0 0 1

1 – 1

1 1 –

1

1


1


1



Упростим F1СДНФ, получим:


F1МДНФ =Основы дискретной математики

Как мы видим, результат, полученный по таблице Куайна, совпадает с F1МДНФ.

Основы дискретной математики


Основы дискретной математики

Рисунок 6.1 – Графический интерфейс


2 Процедура основного обработчика

procedure TForm1. BitBtn1Click (Sender: TObject);

Var i:byte;

x1, x2, x3:boolean;

begin

for i:=1 to 8 do begin

StringGrid1. Cells [0, i]:=IntToStr (i 1);

If i<=4 then StringGrid1. Cells [1, i]:='0' else StringGrid1. Cells [1, i]:='1';

If (i<=2) or ((i>=5) and (i<7)) then StringGrid1. Cells [2, i]:='0' else StringGrid1. Cells [2, i]:='1';

If (i mod 2>0) then StringGrid1. Cells [3, i]:='0' else StringGrid1. Cells [3, i]:='1';

If i<=4 then StringGrid1. Cells [4, i]:='1' else StringGrid1. Cells [4, i]:='0';

If (i<=2) or ((i>=5) and (i<7)) then StringGrid1. Cells [5, i]:='1' else StringGrid1. Cells [5, i]:='0';

x1:=StrToBool (StringGrid1. Cells [1, i]);

x2:=StrToBool (StringGrid1. Cells [2, i]);

x3:=StrToBool (StringGrid1. Cells [3, i]);

if (not (x1) and not (x2) and x3) or (x1 and x3) or (x1 and x2)

then StringGrid1. Cells [6, i]:='1'

else StringGrid1. Cells [6, i]:='0';

end; end;


Пример 2. Пусть будут заданы номера наборов четырех переменных, на которых логическая функция принимает единичное значение: f (2,5,6,7,10,12,13,14)=1.

Выразим эту логическую функцию в СДНФ (символ конъюнкции писать не будем):

f (0010,0101, 0110, 0111, 1010, 1100, 1101, 1110) =


Основы дискретной математики.


Таблица 6.6 – карта Карно для функции 4 х переменных


Основы дискретной математики

Основы дискретной математики

Основы дискретной математики

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: