The Foundations: Logic and Proofs
A truth table is a mathematical table used in logic, e.g. propositions. A truth table can be used to determine whether a proposition is true or false
There are several basic truth tables. In this module, we discuss three truth tables.
1. Negation of a Proposition
Let p be a proposition, the negation of p, denoted as ~p (or ¬p), is the statement “not p”. The truth value of the negation of p, ~p, is the opposite of the truth value of p.
For example, let the proposition p be “Today is Friday”, the negation of p, ~p, is “Today is NOT Friday”. On the other hand, let the proposition p be “Today is NOT Friday”, the negation of p, ~p, is “Today is Friday”.
Another example, let the proposition p be “It is raining outside”, the negation of p, ~p, is “It is NOT raining today”. On the other hand, let the proposition p be “It is NOT raining outside”, the negation of p, ~p, is “It is raining today”
The following table is the truth table for the negation of a proposition p. This table has a row for each o the two possible truth values of a proposition p. Each row shows the truth value of ~p corresponding to the truth value of p for this row.
Table 1: The Truth Table for the Negation of a Propositionp / ~p
T / F
F / T
1. Which of these are propositions? What are the truth values of those that are propositions?
a) Do not pass go. (Not a proposition)
b) What time is it? (Not a Proposition)
c) Miami is the capital of Florida (It is a proposition; it is false)
d) 4 + x = 5 (Not a proposition, declarative sentence but not a statement since it is true or false depending on the value of x)
e) 2 + 3 = 5 (A proposition; it is true)
f) Answer this question (It is not a proposition)
g) There is no pollution in the US (It is a proposition; it is false)
h) The summer in Texas is hot (It is a proposition; it is true)
i) 15 – y =5 (Not a proposition, declarative sentence but not a statement since it is true or false depending on the value of y)
j) 2n > 100 (Not a proposition, declarative sentence but not a statement since it is true or false depending on this variable).
2. Conjunction of Propositions
Let p and q be propositions. The conjunction of p and q, denoted as p^q, is the proposition “p and q”. The conjunction p^q is true when both p and q are true and is false otherwise.
For example, let p be “Today is Friday” and q be “It is raining today”, then the conjunction p^q is “Today is Friday and It is raining today”. This proposition is true on rainy Friday and is false on any day that is not a Friday and on Fridays when it does not rain.
Another example, let p be “Today is NOT Friday” and q be “It is NOT raining today”, then the conjunction p^q is “Today is NOT Friday and It is NOT raining today”. This proposition is true on any day other than rainy Friday, and is false on rainy Friday.
The following table is the truth table for the conjunction of proposition p and q.
Table 2: The Truth Table for the Conjunction of Two Propositionsp / q / p^q
T / T / T
T / F / F
F / T / F
F / F / F
2. Let p and q be the propositions
p: I bought a lottery ticket this week.
q: I won the million dollar jackpot on Friday.
Express of each of these propositions as an English sentence:
a) ~p
I did not buy a lottery ticket this week
b) ~q
I did not win the million dollar jackpot on Friday
c) p^q
I bought a lottery ticket this week and I won the million dollar jackpot.
d) p˅q
Either I bought a lottery ticket this week or I won the million dollar jackpot on Friday.
e) (~p)^( ~q)
I did not buy a lottery ticket this week and I did not win the million dollar jackpot.
f) (~p)˅( ~q)
I did not buy a lottery ticket this week or I did not win the million dollar jackpot.
3. Disjunction of Propositions
Let p and q be propositions. The disjunction of p and q, denoted as p?q, is the proposition “p or q”. The disjunction p?q is false when both p and q are false and is true otherwise.
For example, let p be “Today is Friday” and q be “It is raining today”, then the disjunction p?q is “Today is Friday or It is raining today”. This proposition is true on Fridays or any rainy days and is false on any non-rainy day at is not a Friday.
The following table is the truth table for the disjunction of proposition p and q.
To learn more about truth tables, check the following sites:
1. Simple & Compound Propositions (Pages 1-2) (http://staff.spd.dcu.ie/breens/102notes/Logic1.pdf)
2. Truth tables demo introduction (http://www.youtube.com/watch?v=98jBy8x6HHw)
3. Truth table for basic logic (http://www.youtube.com/watch?v=SRzSZ_rEE_A)
The Foundations: Logic and Proofs
Tautology and Contradiction
Tautology
A compound proposition that is always true, no matter what the truth values of the propositions that occur in it, is called a tautology.
For example p˅(~p) is a tautology because no matter what the truth value p has (either True or False), p˅ (~p) has truth value: True.
Table 1: An Example of a Tautologyp / ~p / p˅ (~p)
T / F / T
F / T / T
For example, let p be “Today is Friday”, then ~p is “Today is NOT Friday”. The disjunction p˅ (~p) is “Today is Friday or Today is NOT Friday”. This proposition is always true on matter whether today is Friday or not.
Contradiction
A compound proposition that is always false, no matter what the truth values of the propositions that occur in it, is called a contradiction
For example p^(~p) is a contradiction because no matter what the truth value p has (either True or False), p^(~p) has truth value: False.
Table 2: An Example of a Contradictionp / ~p / p^(~p)
T / F / F
F / T / F
For example, let p be “Today is Friday”, then ~p is “Today is NOT Friday”. The conjunction p^(~p) is “Today is Friday, and Today is NOT Friday”. This proposition is always false on matter whether today is Friday or not.
To learn more about tautology and contradiction, check the following sites:
1. Tautology Examples (http://www.buzzle.com/articles/tautology-examples.html)
2. Tautology (logic) (http://en.wikipedia.org/wiki/Tautology_%28logic%29)
3. Tautology and Contradiction(http://people.umass.edu/partee/409/Deduction_I.pdf)
Assignment
Let p and q be the propositions
p: I bought a lottery ticket this week.
q: I won the million dollar jackpot on Friday.
1. Form a tautology using p. Express the tautology in English sentence;
If I bought a lottery ticket this week, then I won the million dollar jackpot on Friday.
2. Form a tautology using q. Express the tautology in English sentence;
If I won the million dollar jackpot on Friday, then I bought a lottery ticket this week.
3. Form a contradiction using p. Express the tautology in English sentence;
I bought a lottery ticket this week if and only if I won the million dollar jackpot on Friday.
4. Form a contradiction using q. Express the tautology in English sentence.
I won the million dollar jackpot on Friday if and only if I bought a lottery ticket this week.
How are propositions and tautologies different? Describe their differences with the aid of an example of a proposition and a tautology.
Definition of a set
A set is an unordered collection (or group) of objects. The objects in a set are called elements, or members, of the set.
For example, the set of all vowels in the English alphabet can be written as V = {a, e, i, o, u}. “V” is called the name of the set. The set V contains five elements (or members), a, e, i, o, u.
Another example, the set of days in a week can be written as {Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday}. This set contains 7 element, or members.
An empty set, denoted as ?, is a set which does not have any element.
Set equality
Two sets are equal if and only if they have the same elements.
For example, the sets {1, 3, 5} and {3, 5, 1} are equal, because they have the same elements. So {1, 3, 5} = {3, 5, 1}. Note that the order in which the elements of a set are listed does not matter. Note also that it does not matter if an element of a set is listed more than once, so {1, 3, 3, 5, 5, 5} is the same as the set {1, 3, 5} because they have the same elements.
Definition of a subset
The set A is said to be a subset of the set B if and only if every element of A is also an element of B. We use the notation A B to indicate A is a subset of the B.
For example, A = {1, 2, 3} and B = {1, 2, 3, 4}. A is a subset of B because all the elements in A (1, 2, and 3) are also elements in B. So A B.
For every nonempty set S, there are at least two subsets, the empty set and the set S itself, that is, ? S, and S S. For example, {1, 2, 3} {1, 2, 3}, which means {1, 2, 3} is a subset of itself, {1, 2, 3}.
Definition of a proper subset
A set A is a proper subset of a set B is A is a subset of B but A ≠ B.
For example A={1, 2} and B={1, 2, 3}. A is a proper subset of B because A is a subset of B and A and B are not equal.
However, {1, 2, 3} is NOT a proper subset of {3, 2, 1} because these two sets are the same.
To learn more about sets, check the following sites:
1. Introduction to sets (http://www.mathsisfun.com/sets/sets-introduction.html )
2. Introduction to Sets (http://www.math.fsu.edu/~pkirby/mad2104/SlideShow/s1_1.pdf)
3. Introduction to Set Theory (http://www.cs.odu.edu/~toida/nerzic/content/set/intr_to_set.html)
4. Subset and Proper Subset (http://www.youtube.com/watch?v=9M6x5IoymP4)
Assignment
1. Which of the two sets are equivalent?
a) A = {a, c, b} B = {a, b, c}
b) A = {a, b, c} B = {a, c, d}
c) A = {a, b, c, a, b, c} B = {a, b, c}
2. Given the following set S = {1, 2, 3, 4}
a) Show at least four subsets of S
b) Show at least four proper subsets of S.
Sets and Set Operations
Set Operations
Union of sets
Let A and B be sets. The union of the sets A and B, denoted by A B, is the set that contains those elements that are either in A or in B, or in both.
For example, the union of the sets {1, 3, 5} and {1, 2, 3} is the set {1, 2, 3, 5}; that is, {1, 3, 5} {1, 2, 3} = {1, 2, 3, 5}.
Another example, let A= {all computer science majors at TUI} and B = {all mathematics majors at TUI}. A B = {students at TUI who are majoring either in mathematics or in computer science or both}.
Intersection of sets
Let A and B be sets. The interaction of the sets A and B, denoted by A B, is the set that contains those elements in both A and B.
For example, the interaction of the sets {1, 3, 5} and {1, 2, 3} is the set {1, 3}; that is, {1, 3, 5} {1, 2, 3} = {1, 3}.
Another example, let A= {all computer science majors at TUI} and B = {all mathematics majors at TUI}. A B = {students at TUI who are joint majors in mathematics and computer science}.
Disjoint of sets
Two sets are called disjoint if their interaction is the empty set ?. In another word, the two sets do not share any common element.
For example, the sets {1, 3, 5} and {2, 4, 6} are disjoint. The interaction of the set {1, 3, 5} and the set {2, 4, 6} is an empty set because these two sets do not share any common element.
Difference of sets
Let A and B be two sets. The difference of A and B, denoted by A – B, is the set containing those elements that are in A but not in B.
The difference of A = {1, 3, 5} and B = {1, 2, 3} is the set {5}; that is {1, 3, 5} – {1, 2, 3} = {5} because 5 is an element which is in A but not in B. However, the difference of B and A is the set {2}; that is {1, 2, 3} – { 1, 3, 5} = {2} because 2 is an element which is in B but not in A.
To learn more about set operations, check the following sites:
- Set operations (http://www.cs.odu.edu/~toida/nerzic/content/set/set_operations.html)
- Set Operation: Union (http://www.youtube.com/watch?v=TpiVThfRl0I)
- Intersection and Union of Sets 2.5 (http://www.youtube.com/watch?v=is-74Piys9o)
- Set Theory: Difference (http://www.youtube.com/watch?v=lgvEMS6s-WM)
- Intersection of Sets (http://www.youtube.com/watch?v=4hfiYxDr2SI)
Assignment
1. Let A = {1, 2, 3, 4, 5} and B = {0, 3, 6}. Find:
a) A ∪ B
b) A ∩B
c) A – B
d) B – A
e) Are A and B disjoint sets?
2. Let A = {a, b, c, d, e} and B = {a, b, c, d, e, f, g, h}. Find:
a) A ∪ B
b) A ∩ _
c) A – B
d) B – A
e) Are A and B disjoint sets?
Is a proper subset different from a regular subset? Is an empty set a proper subset? Provide an example of a set to solve for a proper subset and an empty set.
Trees
Basic Tree Concepts
Go to this presentation about trees.To learn more about trees, check the following sites:
- Trees and Traversal (http://www.youtube.com/watch?v=evwGnROlB58)
- Trees (http://en.wikipedia.org/wiki/Tree_%28data_structure%29)
Assignment
1. Given the following tree, fill out the table below
2.
Property / ValuesIs this rooted tree?
Leaf vertices
Intenal vertices
Ancestors of vertice H
Decendants of vertice D
Siblings of vertice G
Parent vertice of F
Trees
Binary Trees
View this presentation on binary trees.