CS 2100 Module 1: Logic Flashcards
What is a proposition?
A statement that can be either true or false nothing else
ex 7 = 5
What is a proposition?
a statement with an ambiguous value or an x
How do we represent propositions?
We use propositional variables, denoted by
lowercase letters, to represent propositions.
ex p = “Today is Wednesday”
Logical operators
combine propositions, Not, And, Or
Not operator
L, turned 270 degrees, flips argument, true if false, false if true
And operator
^ , both are true false otherwise
Or operator
v, at lease one argument is true, can be both true
Or Exclusive
p or q but not both
(p ^ !q) v ( !p ^ q )
Operator precedence
- not
- and
- or
English But Translation
The same as and operator
English neither-nor Translation
not p and not q
Less than or equal to: Translation
a <= b = (a<b) v (a=b)
a <= b <= c = (a <= b) ^ ( b <= c)
What are truth tables?
It tells all possible true values of any compound statement.
Truth Table Not
p: T, f
!p: F, T
Truth Table And
p: T, T, F, F
q: T, F, T, F
p ^ q: T, F, F, F
Truth Table Or
p: T, T, F, F
q: T, F, T, F
p ^ q: T, T, T, F
Logical equivalence
if two statements convey the same logical meaning, or the same value for every row on the truth table, represented by three parallel lines
Logic Laws
t = tautology(always true), c = contradiction(always false)
See useful images.
Substitution rule
We can replace the expression on the left of = with the expression on the right without changing the truth value
tautology
always true
contradiction
always false
Predicate Logic
use variables instead of blanks to form a predicate
x is a CS Major
becomes proposition when x is known
Predicate Domain
Values we use to replace x
Domain of
x is a CS Major
is all students in UoU
Element of
represented as a curvy E
a set (domain)
Sarah E D
means Sarah is a n element od the domain D
