Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


јрифметические действи€ над нормализованными числами




  началу выполнени€ арифметического действи€ операнды операции помещаютс€ в соответствующие регистры јЋ”.

ѕри сложении и вычитании сначала производитс€ подготовительна€ операци€, называема€ выравниванием пор€дков. ¬ процессе выравнивани€ пор€дков мантисса числа с меньшим пор€дком сдвигаетс€ в своем регистре вправо на количество разр€дов, равное разности пор€дков операндов. ѕосле каждого сдвига пор€док увеличиваетс€ на единицу.

¬ результате выравнивани€ пор€дков одноименные разр€ды чисел оказываютс€ расположенными в соответствующих разр€дах обоих регистров, после чего мантиссы складываютс€ или вычитаютс€.

¬ случае необходимости полученный результат нормализуетс€ путем сдвига мантиссы результата влево. ѕосле каждого сдвига влево пор€док результата уменьшаетс€ на единицу.

 

ѕример. —ложить двоичные нормализованные числа 0,10111×2Ц1 и 0,11011×210.

–азность пор€дков слагаемых здесь равна трем, поэтому перед сложением мантисса первого числа сдвигаетс€ на три разр€да вправо.

 

ѕример. ¬ыполнить вычитание двоичных нормализованных чисел 0,10101×210 и 0,11101×21

–азность пор€дков уменьшаемого и вычитаемого здесь равна единице, поэтому перед вычитанием мантисса второго числа сдвигаетс€ на один разр€д вправо

–езультат получилс€ не нормализованным, поэтому его мантисса сдвигаетс€ влево на два разр€да с соответствующим уменьшением пор€дка на две единицы: 0,1101×20.

ѕри умножении двух нормализованных чисел их пор€дки складываютс€, а мантиссы перемножаютс€.

 

ѕример. ¬ыполнить умножение двоичных нормализованных чисел:

 

ѕри делении двух нормализованных чисел из пор€дка делимого вычитаетс€ пор€док делител€, а мантисса делимого делитс€ на мантиссу делител€. «атем в случае необходимости полученный результат нормализуетс€.

ѕример. ¬ыполнить деление двоичных нормализованных чисел:

 

»спользование представлени€ чисел с плавающей точкой существенно усложн€ет схему арифметико-логического устройства.

 

ќсновные пон€ти€ алгебры логики. Ёлементарные логические операции

 ак было отмечено ранее, информатика - прикладна€ наука, наход€ща€с€ на стыке многих наук. ¬месте с тем она опираетс€ на спектр разделов такой фундаментальной наукиї как математика. Ќаиболее важное прикладное значение дл€ информатики имеют булева алгебра, используема€ в разработке алгоритмов программ и в синтезе цифровых устройств.

ќсновное пон€тие булевой алгебры Ч выказывание. ѕод простым высказыванием понимаетс€ повествовательное предложение, о котором можно сказать, истинно оно или ложно (третьего не дано). ¬ысказывани€ обозначаютс€ латинскими буквами и могут принимать одно из двух значений: Ћќ∆№ (обозначим 0) или »—“»Ќј (обозначим 1). Ќапример, содержание высказывани€ ј: Ђдважды два равно четыремї истинно ј = 1, а высказывание ¬: Ђтри больше п€тиї всегда есть Ћќ∆№.

ƒва высказывани€ ј и ¬ называютс€ равносильными, если они имеют одинаковые значени€ истинности, записываетс€ ј = ¬.

—ложное высказывание можно построить из простых с помощью логических операции: отрицани€, конъюнкции, дизъюнкции, импликации и логических выражений, представл€ющих собой комбинации логических операций.

ќперацией отрицани€ ј называют высказывание (говор€т Ђне јї), которое истинно тогда, когда ј ложно, и ложно тогда, когда ј истинно. Ќапример, если событие ј состоит в том, что Ђзавтра будет снегї, то ј Ђзавтра Ќ≈ будет снегаї, истинность одного утверждени€ автоматически означает ложность второго. ќтрицание - унарна€ (т.е. дл€ одного операнда) логическа€ операци€. ≈й соответствует €зыкова€ конструкци€, использующа€ частицу Ќ≈.

Ёто правило можно записать в виде следующей таблицы:

 

ј
   
   

 

“ака€ таблица называетс€ таблицей истинности.

 онъюнкцией (логическим умножением) двух высказываний ј и ¬ €вл€етс€ новое высказывание —, которое истинно только тогда, когда истинны оба высказывани€, записываетс€ — = ј Ù ¬ или — = ј & ¬ (при этом говор€т Ђ— равно ј и ¬ї). ѕримером такой операции может быть следующа€: пусть высказывание ј состоит в том, что Ђвысота шкафа меньше высоты двериї, событие ¬ Ђширина шкафа меньше ширины двериї, событие — Ђшкаф можно внести в дверь, сели ширина шкафа меньше ширины двери » высота шкафа меньше высоты двериї, т.е. данна€ операци€ примен€етс€, если два высказывани€ св€зываютс€ союзом ».

“аблица истинности этой операции, как следует из определени€, имеет вид

 

ј ¬ ј & ¬
     
     
     
     

 

ƒизъюнкцией (логическим сложением) двух высказываний ј и ¬ €вл€етс€ новое высказывание —, которое истинно, если истинно хот€ бы одно высказывание. «аписываетс€ — = A Ú ¬ (при этом говор€т: Ђ— равно ј »Ћ» ¬). ѕример такой операции следующий: пусть высказывание ј состоит в том, что Ђстудент может добиратьс€ домой на автобусеї, событие ¬ Ђстудент может добиратьс€ домой на троллейбусеї, событие — Ђстудент добралс€ домой на автобусе »Ћ» троллейбусеї, т.е. данна€ операци€ примен€тс€, если два высказывани€ св€зываютс€ союзом »Ћ».

“аблица истинности такой операции следующа€:

 

ј ¬ A Ú ¬
     
     
     
     

 

»мпликацией двух высказываний ј (ј называетс€ посылкой) и ¬ (¬ называетс€ заключением) €вл€етс€ новое высказывание —, которое ложно только тогда, когда посылка истинна, а заключение ложно, записываетс€ — = ј Ѓ ¬ (при этом говор€т: Ђиз ј следует ¬ї). ѕримером такой операции может быть любое рассуждение типа: если произошло событие ј, то произойдет событие ¬, Ђесли идет дождь, то на небе тучиї. ќчевидно, операци€ не симметрична, т.е. из ¬ Ѓ ј не всегда истинно, в нашем примере Ђесли на небе тучи, то идет дождьї не всегда истинно.

“аблица истинности импликации следующа€:

 

ј ¬ ј Ѓ ¬
     
     
     
     

 

»мпликаци€ имеет следующие свойства:

ј Ѓ ¬ ≠ ¬ Ѓ ј

ј Ѓ ј = 1

0 Ѓ ј = 1

1 Ѓ ј = ј

ј Ѓ 1 = 1

ј Ѓ 0 =

Ёквиваленцией двух высказываний ј и ¬ €вл€етс€ новое высказывание —, которое истинно только тогда, когда оба высказывани€ имеют одинаковые значени€ истинности, записываетс€ — = ј Ђ¬ (.— = ј º ¬). ѕримером такой операции может быть любое высказывание типа: событие ј равносильно событию ¬.

“аблица истинности:

 

ј ¬ ј Ђ¬
     
     
     
     

 

Ёквиваленци€ имеет следующие свойства:

ј Ђ¬ = ¬ Ђј

ј Ђ¬ = Ђ

ј Ђ1 = ј

ј Ђ0 =

 

— помощью логических операций из простых высказываний (логических переменных и констант) можно построить логические выражени€, которые также называютс€ булевскими функци€ми. Ќапример, — = (( Ú ¬) Ѓ ¬) Ú ј.

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

ќперации не €вл€ютс€ независимыми; одни из них могут быть выражены через другие. ћожно доказать с помощью таблиц истинности следующие равносильности:

 

 

ќдну и ту же зависимость между логическими переменными можно выразить различными формулами. ѕоэтому важно иметь возможность приводить формулы с помощью эквивалентных преобразований к некоторому стандартному виду. —уществует несколько стандартных форм, к которым привод€тс€ логические выражени€ с помощью эквивалентных преобразований (формулы 1 - 23).

ѕерва€ из них Ц дизъюнктивна€ нормальна€ форма (ƒЌ‘), имеет вид

 

A1 Ú ј2 Ú Е Ú јn,

 

где каждое из составл€ющих высказываний есть конъюнкци€ простых высказываний и их отрицаний, например: ¬ = ( & ј2 & A3) Ú (ј4 & ј5).

¬тора€ Ц конъюнктивна€ нормальна€ форма ( Ќ‘), имеет вид

 

A1 Ù ј2 Ù Е Ù јn,

 

где каждое из составл€ющих есть дизъюнкци€ √фостых высказываний и их отрицаний, например: ¬ = ( Ú ј2 Ú ) & (ј4 Ú ј5) & ј6.

«адать булевскую функцию можно, определ€€ ее значени€ дл€ всех наборов значений аргументов.  аждый аргумент может иметь два значени€: 0 и 1, следовательно, n аргументов могут принимать 2n различных наборов. ѕусть, например, булевска€ функци€ имеет три аргумента: ’1, X2, ’3. ќбщее число наборов 23 = 8. «ададим таблицу истинности функции, указав дл€ каждого набора значение функции.

 

 

¬ комбинаци€х, где функци€ принимает значение 1, единица замен€етс€ именем функции, а нуль Ч именем с отрицанием (т.е. комбинации 0 0 1 ставитьс€ в соответствие выражение & &X3), все элементы соедин€ютс€ знаками дизъюнкции.

ƒл€ рассматриваемого примера получим

F(X1, ’2, X3) = ( & &X3)Ú( & ’2 & X3)Ú(’1 & &X3) Ú(’1&’2&X3).

 ак нетрудно заметить, построенна€ функци€ удовлетвор€ет заданной таблице истинности. ‘ункци€ представл€ет дизъюнктивную нормальную форму.  роме того, в каждую группу дизъюнкций вход€т все аргументы функции. “ака€ ƒЌ‘ называетс€ совершенной, а кажда€ группа дизъюнкций называетс€ коституентой единицы.

јналогично, дл€ комбинаций, где функци€ принимает значение нул€, можно построить алгебраическую форму

F(X1, ’2, X3) = (’1Ú’2ÚX3) & (’1Ú ÚX3) & ( Ú’2ÚX3) & ( Ú ÚX3),

котора€ также удовлетвор€ет заданной таблице истинности и представл€ет собой конъюнктивою нормальную форму, в данном случае совершенную.  ажда€ конъюнкци€ называетс€ конституентой нул€.

 





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2016-11-12; ћы поможем в написании ваших работ!; просмотров: 2940 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

Ћюди избавились бы от половины своих непри€тностей, если бы договорились о значении слов. © –ене ƒекарт
==> читать все изречени€...

1539 - | 1348 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.018 с.