Discrete IIChapter 17.1 Boolean Logic Notes – Binary Codes
Name:______
Objective: The learner will be able to use the Venn Diagram method to code 4-digit binary messages into 7-digit code words and to determine ho to correct single digit errors in coding.
______
A. Code Words
1. Using 1 or 0 each circle must be an even amount.
2. Place 0 or 1 in positions 5,6,7 to make each circle add up to an even number.
Such as 0, ,2, 4
This is called Even Parity.
Use theVenndiagram method to append three check digits onto the following messages, creating a seven-digit code word. Complete the table below.
1)put the digits in order into the Venn diagram
2)the remaining areas (5, 6, 7) are assigned 0 or 1 to make the numer of 1’s in each circle even.
3)The 7-digit code word lists the digits of the seven areas in order.
Message / Code word / Message / Code Word0000 / 0111
0001 / 1001
0010 / 1010
0100 / 1100
1000 / 1011
0011 / 1101
0101 / 1110
0110 / 1111
Objective: to check and recode a given message.
1)enter the given message into the Venn Diagram and check to see if each circle is even.
2)If all circles are even, the message is coded properly.
3)If one or more circles are odd, change ONE area in the diagram to make them all even.
4)List the recoded message
Code Received / Message received / Coded properly? (Y/N) / Corrected code / Actual message1. / 0001000
2. / 0110011
3. / 0110000
4. / 1100101
5. / 1111100
6. / 0111100
7. / 1101000
8. / 0110010
9. / 0011100
10. / 0111101
11 / 1111000
12. / 0101000
13. / 0001010
14. / 0111001
15. / 0011110
16. / 0111000
17. / 0001111
18. / 0111010
Discrete IIChapter 17.2 Boolean Logic Notes – Nearest Neighbor Decoding
Name:______
Objective(s): The learner will be able to use Nearest Neighbor decoding to decode received code words with two or more possible errors.
distance between two strings: number of positions in which two code words differ
Find the distance between each of the following pairs of words. (How many digits are different?)
1. 11011011 and 10100110 2. 110101 and 111110 3.1011111 and 1101111 4. 1010110 and 1000110
Nearest Neighbor method: 1) find the distance between the received code word and each possible code word
2) decode as the possible code word with the smallest distance from the received code word
3) if 2 code words have the same smallest distance from the received code word, there is no code word
Possible
Code Words1) for the received code word 0001001, use the nearest neighbor method to find
A0000000the best possible code word
B0001011
C0010110distances:A =B =C = D = E = F = G = H =
D0100101I = J = K = L = M = N = O = P =
E1000111
F0011101best possible code word =
G0101110
H01100112) for the received code word 1001001, use the nearest neighbor method to find
I0111000 best possible code word
J1001100
K1010001 distances:A =B =C = D = E = F = G = H =
L1100010I = J = K = L = M = N = O = P =
M1011010
N1101001 best possible code word =
O1110100
P1111111
Possible
Code Words3) for the received code word 1100111, use the nearest neighbor method to find
A0000000the best possible code word
B0001011
C0010110distances:A =B =C = D = E = F = G = H =
D0100101I = J = K = L = M = N = O = P =
E1000111
F0011101best possible code word =
G0101110
H01100114) for the received code word 0011001, use the nearest neighbor method to find
I0111000 best possible code word
J1001100
K1010001 distances:A =B =C = D = E = F = G = H =
L1100010I = J = K = L = M = N = O = P =
M1011010
N1101001 best possible code word =
O1110100
P1111111
Name: ______Date ______
Discrete Math 2: 17.2 – Nearest Neighbor Decoding (Page 2)
Objective(s): The learner will be able to use Nearest Neighbor decoding to decode received code words with two or more possible errors.
Possible
Code Words1) for the received code word 1000111, use the nearest neighbor method to find
A0000000the best possible code word
B0001011
C0010110distances:A =B =C = D = E = F = G = H =
D0100101I = J = K = L = M = N = O = P =
E1000111
F0011101best possible code word =
G0101110
H01100112) for the received code word 1000001, use the nearest neighbor method to find
I0111000 best possible code word
J1001100
K1010001 distances:A =B =C = D = E = F = G = H =
L1100010I = J = K = L = M = N = O = P =
M1011010
N1101001 best possible code word =
O1110100
P1111111
Possible
Code Words3) for the received code word 0001000, use the nearest neighbor method to find
A0000000the best possible code word
B0001011
C0010110distances:A =B =C = D = E = F = G = H =
D0100101I = J = K = L = M = N = O = P =
E1000111
F0011101best possible code word =
G0101110
H01100114) for the received code word 0111101, use the nearest neighbor method to find
I0111000 best possible code word
J1001100
K1010001 distances:A =B =C = D = E = F = G = H =
L1100010I = J = K = L = M = N = O = P =
M1011010
N1101001 best possible code word =
O1110100
P1111111
5) For each of the codes in 1-4, assume they are 1-digit errors. Check them using Venn diagrams to determine which digit needs to be corrected to make them valid codes.
a) 1000111b) 1000001c) 0001000d) 0111101
Name: ______Date ______
Discrete Math 2: 17.3 – Data Compression (Page 1)
Objective(s): The learner will be able to compress data into more efficient codes and read codes from compressed data.
To compress data:1) determine which characters are used the most and the least
2) assign shorter codes to more often used characters & longer to least often used ones
3) write the message
all code assignments end in 0 except the last one, which is all 1’s
for 3 characters: most used = 0, then 10, and 11
for 4 characters: 0, 10, 110, 111
for 8 characters: 0, 10, 110, 1110, 11110, 111110, 1111110, 1111111
What would be a good assignment for 7 characters?
1) original message: ACE DECADE DAD A BAD CAB FAD
a) encode using the standard decoding of: A = 000, B = 001, C = 010, D = 011, E = 111, F = 110
code:
how many characters?:
b) encode by compressing the data
i) how often is each character used: A = ___, B = ___, C = ___, D = ___, E = ___, F = ___
ii) assign a code based on step i): A = ____, B = ____, C = ____, D = ____, E = ____, F = ____
new code:
how many characters?:
2) original message: BDEDA CDBCB ADEED BBDAD CCDDE
a) encode using the standard decoding of: A = 000, B = 001, C = 010, D = 011, E = 111
code:
how many characters?:
b) encode by compressing the data
i) how often is each character used: A = ___, B = ___, C = ___, D = ___, E = ___, F = ___
ii) assign a code based on step i): A = ____, B = ____, C = ____, D = ____, E = ____, F = ____
new code:
how many characters?:
B. Data Compression: Decode and encode phrases using binary representation.
Given: A = 00c = 01T = 10G = 11
1. Encode AAACAGTAAC
2. Encode AGAACTAATTGACA
3. Decode: 0011010110101000
Given: A = 0C = 10 T = 110G = 111
4. Encode AAACAGTAAC
5. Encode AGAACTAATT
6. Decode: 0011010110101110
Given: A = 1111B = 1110 C = 01 D = 110 E = 00 F = 10 (Huffman Code)
7. Encode AABFFCBEFDE
8. Decode: 11101000011010011111010010
Name: ______Date ______
Discrete Math 2: 17.3 – Decoding Compressed Data (Page 2)
Objective(s): The learner will be able to decodecompressed data.
1) Encode the following sequences using the given encoding schemes:
a) sequenceABCCBAscheme: A 0, B 10, C 11
code:
b) sequenceABACABscheme: A 0, B 10, C 11
code:
c) sequenceAACBCDABscheme: A 0, B 10, C 110,D 111
code:
d) sequenceAAACAGTAACscheme: A 0, C 10, T 110,G 111
code:
2) Decode the following using the given encoding schemes:
a) code011001010110scheme: A 0, B 10, C 11
sequence:
b) code1101110111100scheme: A 0, B 10, C 11
sequence:
c) code0111110011110110010scheme: A 0, B 10, C 110,D 111
sequence:
d) code01101111110111111101101010scheme: A 0, C 10, T 110, G 1110, D 1111
sequence:
e) code0110110111100110111111scheme: A 0, B 10, C 110, D 111
sequence:
f) code 1111111111100010011010110scheme: X 0, Y 10, Z 110,W 1110, V 1111
sequence:
g) code01101111111010100011101000scheme: A 0, B 10, C 110, D 1110, E 1111
sequence:
3) Decode the following using the given encoding schemes:
a) code101110010110scheme: A 0, B 10, C 11
sequence:
b) code001101110110011111100scheme: A 0, B 10, C 11
sequence:
c) code1111100001100001110010scheme: A 0, B 10, C 110,D 111
sequence:
d) code1100110010011101111011111100scheme: A 0, C 10, T 110, G 1110, D 1111
sequence:
e) code0111111101110101110101000111110110000
scheme: A 0, B 10, C 110, D 1110, E 11110,F 111110, G 111111
sequence:
f) code11111111111011111011010110111101111011111111111110111101110
scheme: X 0, Y 10, Z 110,W 1110, V 11110,Z 111110,W 1111110, V 1111111
sequence:
g) code001111110101101111011110111111100010110110101110111101111110011000
scheme: A 0, B 10, C 110, D 1110, E 11110,F 111110, G 1111110, H 1111111
sequence:
h) code001111110101101111011110111111100010110110101110111101111110011000
scheme: A 0, B 10, C 110, D 1110, E 11110,F 111110, G 111111
sequence:
h) code001111110101101111011110111111100010110110101110111101111110011000
scheme: A 0, B 10, C 110, D 1110, E 11110,F 11111
sequence:
Name: ______Date ______
Discrete Math 2: 17.4 – Cryptology – Caesar Cipher
Objective(s): The learner will be able to decode quotes using Caesar cipher-like encoding strategies.
Cryptography – the study of methods to make and break secret codes.
Caesar Cipher – one of the first known methods. Used by Julius Caesar to send messages to troops. Every letter is shifted over by 3. A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
1. Encode ATTACK AT DAWN .2. Decode the message “BRX MXVW VWDEEHG PH.”
3. Encode MEET AT JOES 4. Encode the message “ET TU BRUTUS.”
5. Encode the message “WARNING AMBUSH AHEAD”
6. Decode the message “BRX KDYH FRPSOHWHG SUREOHP WZR”
7. Decode the message “WKLV SUREOHP ZDV KDUG EXW BRX GLG LW”
8. Decode the message “FDHVDU FLSKHUV DUH HDVB”
9. Encode the message “I LOVE DISCRETE MATH”
10. Decode the message “LP JRRG DW WKLV” 11. Encode the message “CODING IS FUN”
12. Decode the message “NDSODQ LV D FUDCB WHDFKHU” 13. Encode the message “GO HOME NOW”
14. Decode the message “PB PLQG LV EORZQ”
15. Encode the message “THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG”
16. Decode the message “RQFH L ILQLVK LP GRQH IRU WKH SHULRG”
Name: ______Date ______
Discrete Math 2: 17.4 – Cryptology – Caesar Cipher - A
1. a. Enrypt “keep this secret” with a shift of 3.
b. Encrypt your teacher’s name with a shift of 3.
Decrypt the answers to the following riddles. They were encrypted using a Caesar cipher with a shift of 3.
2a. Riddle: What do you call a sleeping bull?
b. Riddle: What’s the difference between a teacher and a train?
Create a Caesar cipher with shift of 4:
A / B / C / D / E / F / G / H / I / J / K / L / M / N / O / P / Q / R / S / T / U / V / W / X / Y / Z3. Decrypt the following note Evie wrote to Abby. She used a Caesar cipher with a shift of 4
Decrypt each answer by first figuring out the shift. Let the one-letter words help you.
4a. Riddle: What do you call a happy Lassie?
b. Riddle: Knock, knock. Who’s there? Cash. Cash who?
c. Riddle: What’s the noisiest dessert?
Name: ______Date ______
Discrete Math 2: 17.4 – Cryptology – Caesar Cipher - B
Decode the following quotes. Theyuse a Caesar cipher but are shifted a different number of spaces than three. Good luck!
ABCDEFGHIJKLMNOPQRSTUVWXYZ
encrypted code:
1) “QEB BKBJV LC QEB YBPQ FP QEB DLLA BKLRDE.” -- OLDBO YOBFAFKDBO
______
ABCDEFGHIJKLMNOPQRSTUVWXYZ
encrypted code:
2) “RC CF RC BCH. HVSFS WG BC HFM.” -- MCRO
______
ABCDEFGHIJKLMNOPQRSTUVWXYZ
encrypted code:
3) “TW CAFV OZWFWNWJ HGKKATDW. AL AK SDOSQK HGKKATDW.” -- VSDSA DSES
______
ABCDEFGHIJKLMNOPQRSTUVWXYZ
encrypted code:
4) “TWOBVX BL PATM PX TLD YHK PAXG PX TEKXTWR DGHP MAX TGLPXK UNM PBLA PX WBWG’M.” -- XKBVT CHGZ
______
ABCDEFGHIJKLMNOPQRSTUVWXYZ
encrypted code:
5) “JZF XFDE MP ESP NSLYRP JZF HLYE EZ DPP TY ESP HZCWO.” -- RLYOST
______
ABCDEFGHIJKLMNOPQRSTUVWXYZ
encrypted code:
6) “MU QHU MXQJ MU HUFUQJUTBO TE. UNSUBBUDSU, JXUD, YI DEJ QD QSJ RKJ Q XQRYJ.” -- QHYIJEJBU
______
ABCDEFGHIJKLMNOPQRSTUVWXYZ
encrypted code:
7) “C BUPY GUXY NBCM FYNNYL FIHAYL NBUH OMOUF VYWUOMY C FUWE NBY NCGY NI GUEY CN MBILNYL.” -- VFUCMY JUMWUF
Name: ______Date ______
Discrete Math 2: 17.4 – Cryptology – Decimation Cipher
Objective(s): The learner will be able to decode quotes using Decimation cipher-like encoding strategies.
Decimation Cipher: start at A, count by the key (k), continue counting by wrapping until all letters are rewritten.
A / B / C / D / E / F / G / H / I / J / K / L / M / N / O / P / Q / R / S / T / U / V / W / X / Y / Z1. Encode ATTACK AT DAWN with key = 5.
2. Encode MEET AT JOES with k = 3
3, Encode the mesasage“HASTA LA VISTA BABY” with k = 3. .
4. Encode the message “AFFINE CIPHER” using k = 5.
5. Encode the message “DRINK YOUR OVALTINE” using k = 3
6. Decode the message “ZHANYDQ IQ PUAH O PSNR EOBU A PAIN” using k = 5 .
7. Decode the message “VQICFQN OM VALM A TZQDHMK” What key makes sense, 3 or 5?
Name: ______Date ______
Discrete Math 2: 17.4 – Cryptology – Decimation Cipher A
Objective(s): The learner will be able to decode quotes using Decimation cipher-like encoding strategies.
1) a) Complete the table with key = 3.
A / B / C / D / E / F / G / H / I / J / K / L / M / N / O / P / Q / R / S / T / U / V / W / X / Y / Zb) Decrypt the following message Evie wrote using a key of 3.
JAN, Y ENQO OVAF UQI OZQFM.
c) Riddle: What has one foot on each end and one foot in the middle?
Decrypt the answer
Answer: A UAZJCFYGE
2) a) Complete the table with key = 7.
A / B / C / D / E / F / G / H / I / J / K / L / M / N / O / P / Q / R / S / T / U / V / W / X / Y / Zb) Decrypt the following quote.
UKP OXAPAODCP EW YXAD YC VU YXCN YC DXENS NU UNC EW ZUUSENQ.
-H. Jackson Brown, Jr.
3) a) Complete the table with key = 5.
A / B / C / D / E / F / G / H / I / J / K / L / M / N / O / P / Q / R / S / T / U / V / W / X / Y / ZDecrypt the following quotes.
FU MWHU QSW XWR QSWH ZUUR ON RJU HOEJR XDAKU, RJUN MRANP
ZOHI.
-Abraham Lincoln
c) RJU OIXSHRANR RJONE OM NSR RS MRSX CWUMROSNONE.
-Albert Einstein
4) a) Complete the table with key = 9.
A / B / C / D / E / F / G / H / I / J / K / L / M / N / O / P / Q / R / S / T / U / V / W / X / Y / Zb) Decrypt the following quote.
PLK EWGP KZLAYGPUNC PLUNC UN VUTK UG JKUNC UNGUNSKXK.
-Anne Morrow Lindbergh
Name: ______Date ______
Discrete Math 2: 17.5 – Truth Tables
Objective(s): The learner will be able to determine true or false statements using truth tables.
Truth Tables: uses Boolean Logic, which is a statement that is either true or false.
•The expression NOT P is called the negation of P. If P is true then NOT P is false, and if P is false then NOT P is true. The
standard mathematical notation for this is ¬P or ~P.
Example:
Given: / Let p represent the sentence "The number 9 is odd."Problem: / What does ~p mean?
Since p is ______, ~p must be ______.
Example:
Given: / Let p represent, "Baseball is a sport."Let q represent, "There are 100 cents in a dollar."
Let r represent, "She does her homework."
Let s represent, "A dime is not a coin."
Problem: / Write each sentence below using symbols and indicate if it is true, false or neither.
1. / A dime is a coin.
2. / Baseball is not a sport.
3. / She does her homework.
4. / There are not 100 cents in a dollar.
5. / She does not do her homework.
6. / Baseball is a sport.
We can construct a truth table to determine all possible truth values of a statement and its negation.
Definition: / A truth table helps us find all possible truth values of a statement. Each statement is either True (T) or False (F),but not both. /
Example: / Construct a truth table for the negation of x.
Conjunction (“and” )
Example: /
Given: / p: Ann is on the softball team.
q: Paul is on the football team.
Problem: / What does pq represent?
Solution:
Definition: / A conjunction is a compound statement formed by joining two statements with the connector ______. The conjunction "p and q" is symbolized by p____q. A conjunction is true when both of its combined parts are true; otherwise it is false.
Now that we have defined a conjunction, we can apply it to the Example. The conjunction pq is true when both "Ann is on the softball team" and "Paul is on the football team" are true statements; otherwise it is false.
•The truth table is as follows.
p / q / pqT / T
T / F
F / T
F / F
Example:
Given: / a: A square is a quadrilateral.
b: Harrison Ford is an American actor.
Problem: / Construct a truth table for the conjunction "a and b." Also write out the sentence the expression creates.
Solution
a / b / ab
T / T
T / F
F / T
F / F
Example 4:
Given: / p: The number 11 is prime. / true
q: The number 17 is composite. / false
r: The number 23 is prime. / true
Problem: / For each conjunction below, write a sentence and indicate if it is true or false.
1. / pq
2. / pr
3. / qr
Example 5: / Construct a truth table for each conjunction below:
1. / ~x and y
2. / ~y and x
/
Disjunction (“OR” )
Example: /
Given: / p: Ann is on the softball team.
q: Paul is on the football team.
Problem: / What does pq represent?
In Example, statement p represents, "Ann is on the softball team" and statement q represents, "Paul is on the football team." The symbol _____is a logical connector which means "____." Thus, the compound statement pq represents the sentence, "Ann is on the softball team or Paul is on the football team." The statement pq is a disjunction. . A disjunction is false if and only if both statements are false; otherwise it is true
p / q / pq
T / T
T / F
F / T
F / F
Example 4:
Given: / p: 12 is prime. / false
q: 17 is prime. / true
r: 19 is composite. / false
Problem: / Write a sentence for each disjunction below. Then indicate if it is true or false.
1. / pq
2. / pr
3. / qr
Example 5: / Complete a truth table for each disjunction below.
1. / a or not b
2. / not a or b
3.
P / Q / ⌐Q / P ∧ Q / (P ∧Q) ∨ ⌐QT / T
T / F
F / T
F / F
4.
P / Q / ⌐Q / P ∨ Q / (P ∨Q) ∨ ⌐QT / T
T / F
F / T
F / F
Convert the sentence to a logic expression.
1) MOVIES AND POPCORN
2) MOVIES AND NOT POPCORN
3) NOT MOVIES AND NOT POPCORN
4) MOVIES AND (POPCORN OR CANDY)
5) MOVIES OR (POPCORN AND NOT CANDY)
Conditional StatementsDefinition: / A conditional statement, symbolized by pq, is an ______statement in which p is a hypothesis and q is a conclusion. The logical connector in a conditional statement is denoted by the symbol ______. The conditional is defined to be true unless a true hypothesis leads to a false conclusion. A truth table for pq is shown below.
Example 1: Fill in the truth table and write a sentence. /
Given: / p: I do my homework.
q: I get my allowance.
p / q / pq
T / T
T / F
F / T
F / F
In the following examples, we are given the truth values of the hypothesis and the conclusion and asked to determine the truth value of the conditional.
Example 4: What is the truth value ofrs?
Given: / r: 8 is an odd number. / false
s: 9 is composite. / true
Example 5: Write each conditional below as a sentence. Then indicate its truth value.
Given: / p: 72 = 49. / true
q: A rectangle does not have 4 sides. / false
r: Harrison Ford is an American actor. / true
s: A square is not a quadrilateral. / false
/
1. / pq
2. / qr
3. / pr
4. / qs
5. / r~p
6. / ~rp
Compound Statements In this lesson, we will learn how to determine the truth values of a compound statement with the logical connectors ~, , and .
Example 1:
Given: / p: 72 = 49 / true
q: A rectangle does not have 4 sides. / false
r: Harrison Ford is an American actor. / true
Problem: / Write each sentence below in symbolic form. Then determine its truth value.
/
1. / If 72 = 49, then a rectangle has 4 sides.
2. / If 7249, then a rectangle does not have 4 sides.
3. / If a rectangle has 4 sides, then Harrison Ford is not an American actor.
4. / If Harrison Ford is an American actor, then 7249.
5. / If 72 = 49 or a rectangle does not have 4 sides, then Harrison Ford is not an American actor.
What are the truth values of the following compound statements?
1) ~p(qp) 5) q (p~q)
2) (pq)q 6) ~b(ab)
3) (sr)~r 7) (ab)a
4) (pq)~q8) ~p (p q)
Equivalence /We will use Boolean logic to decide whether 2 statements have the same meaning. Example: Is “football and (not nfl) and (not college)” equivalent to “football and not (nfl or college)” ?
Example 1:Are the following equivalent? /Given: / ~pq / If I don't study, then I fail.
pq / I study or I fail.
p / q / ~p / ~pq / pq
T / T / F
T / F / F
F / T / T
F / F / T
In the truth table above, the last two columns have the same exact truth values! Therefore, the statement ~pq is logically equivalent to the statement pq.
Definition: / When two statements have the same exact truth values, they are said to be logically equivalent.
Construct a truth table for each statement below. Then determine which two are logically equivalent.
1. / ~qp2. / ~(pq)
3. / pq
2) Is p~q or pq or ~(pq) logically equivalent?
3) Show that p → q and ⌐q → ⌐p are logically equivalent by using a truth table.
- 1 -