Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Discrete math > discrete math 1 midterm > Flashcards

discrete math 1 midterm Flashcards

1
Q

proposition

A

A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both. All the following declarative sentences are propositions. 1. Washington, D.C., is the capital of the United States of America. 2. Toronto is the capital of Canada. 3. 1 + 1 = 2. 4. 2 + 2 = 3.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

propositional variables

A

variables that represent propositions, just as letters are used to denote numerical variables. The conventional letters used for propositional variables are p, q, r, s, . . . . The truth value of a proposition is true, denoted by T, if it is a true proposition, and the truth value of a proposition is false, denoted by F, if it is a false proposition.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

propositional calculus

A

The area of logic that deals with propositions The area of logic that deals with propositions is called the propositional calculus or propositional logic. It was first developed systematically by the Greek philosopher Aristotle more than 2300 years ago.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

compound propositions

A

formed from existing propositions using logical operators

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

truth table

A

a diagram in rows and columns showing how the truth or falsity of a proposition varies with that of its components.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

negation operator

A

¬p

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

conjunction operator

A

ᐱ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

disjunction operator

A

ᐯ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

p ∧ q

A

conjunction “and”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

p ∨ q

A

disjunction “or”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

¬p

A

negation “not”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

inclusive or

A

p ∨ q “disjunction” p or q (but not both)”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

conditional operator

A

→ The conditional statement p → q is false when p is true and q is false, and true otherwise

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

→

A

conditional statement

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

implication

A

→ A conditional statement is also called an implication

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

“If I am elected, then I will lower taxes.”

A

conditional statement

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

if 2 + 2 = 4 then x := x + 1

A

conditional statement

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

CONVERSE

A

one of three related conditional statements that occur so often that they have special names q → p is called the converse of p → q

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

CONTRAPOSITIVE

A

one of three related conditional statements that occur so often that they have special names p → q is the proposition ¬q →¬p

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

INVERSE

A

one of three related conditional statements that occur so often that they have special names ¬p →¬q is called the inverse of p → q

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

equivalent

A

When two compound propositions always have the same truth value. conditional statement and its contrapositive are equivalent: p → q = ¬q →¬p “If it is raining, then the home team wins.” “If the home team does not win, then it is not raining.”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

biconditional statement

A

p ↔ q proposition “p if and only if q.” also called bi-implications

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

p ↔ q

A

biconditional proposition “p if and only if q.”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

bi-implications

A

p ↔ q proposition “p if and only if q.” also called biconditional statement

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

“if and only if”

A

biconditional statement p ↔ q

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

“q whenever p”

A

→ conditional statement

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

“not”

A

negation operator ¬p

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

p → q “p only if q” Is Same As ?

A

“if p, then q,”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

¬p →¬q

A

inverse

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

q → p is considered what of p → q

A

converse

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

p → q is considered what of ¬q →¬p

A

contrapositive

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

¬p →¬q is considered what of p → q

A

inverse

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

What are the contrapositive, the converse, and the inverse of the conditional statement “The home team wins whenever it is raining?”

A

Consequently, the contrapositive of this conditional statement is “If the home team does not win, then it is not raining.” The converse is “If the home team wins, then it is raining.” The inverse is “If it is not raining, then the home team does not win.” Only the contrapositive is equivalent to the original statement.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

“iff”

A

“if and only if.” biconditional statement p ↔ q

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

(p → q) ∧ (q → p).

A

Note that p ↔ q has exactly the same truth value as (p → q) ∧ (q → p). **** biconditional statement ****

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

What is the Precedence of Logical Operator →

A

¬ 1 ∧ 2 ∨ 3 → 4 ↔ 5

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

What is the Precedence of Logical Operator ¬

A

¬ 1 ∧ 2 ∨ 3 → 4 ↔ 5

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

What is the Precedence of Logical Operator ↔

A

¬ 1 ∧ 2 ∨ 3 → 4 ↔ 5

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

What is the Precedence of Logical Operator ∨

A

¬ 1 ∧ 2 ∨ 3 → 4 ↔ 5

40
Q

What is the Precedence of Logical Operator ∧

A

¬ 1 ∧ 2 ∨ 3 → 4 ↔ 5

41
Q

What logic gate is this?

A

Inverter

42
Q

What logic gate is this?

A

OR gate

43
Q

what logic gate is this?

A

AND gate

44
Q

What is a A combinatorial circuit?

A

Complicated digital circuits can be constructed from three basic circuits, called gates, shown

in Figure 1. The inverter, or NOT gate, takes an input bit p, and produces as output °˛p. The

OR gate takes two input signals p and q, each a bit, and produces as output the signal p ∨ q.

Finally, the AND gate takes two input signals p and q, each a bit, and produces as output the

signal p ∧ q.

45
Q

tautology

A

A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it, is called a tautology

46
Q

contradiction.

A

A compound proposition that is always false is called a contradiction.

47
Q
A
48
Q

contingency.

A

A compound proposition that is neither a tautology nor a

contradiction is called a contingency

49
Q

logically equivalent

A

Compound propositions that have the same truth values in all possible cases are called logically equivalent.

≡

50
Q

≡

A

Compound propositions that have the same truth values in all possible cases are called logically equivalent

51
Q

p ≡ q

A

is the statement that p ↔ q is a tautology

52
Q

De Morgan’s Laws.

A

named after the English mathematician Augustus De Morgan, of the mid-nineteenth century

¬(p ∧ q) ≡ ¬p ∨¬q

¬(p ∨ q) ≡ ¬p ∧¬q

53
Q

Identity laws

A
54
Q

Domination laws

A
55
Q

Idempotent laws

A
56
Q

Double negation law

A
57
Q

Commutative laws

A
58
Q

Associative laws

A
59
Q

Distributive laws

A
60
Q

De Morgan’s laws

A
61
Q

Absorption laws

A
62
Q

Negation laws

A
63
Q

De Morgan’s laws are particularly important because?

A

They tell us how to negate conjunctions and how to negate disjunctions.

In particular, the equivalence ¬(p ∨ q) ≡ ¬p ∧¬q tells us that the negation of a disjunction is formed by taking the conjunction of the negations of the component propositions. Similarly, the equivalence ¬(p ∧ q) ≡ ¬p ∨¬q tells us that the negation of a conjunction is formed by taking the disjunction of the negations of the component propositions

64
Q

Propositional Satisfiability

A

A compound proposition is satisfiable if there is an assignment of truth values to its variables that makes it true

65
Q

Propositional unsatisfiable.

A

when the compound proposition is false for all assignments of truth values to its variables, the compound proposition is unsatisfiable.

to show that a compound proposition is unsatisfiable, we need to show that every assignment of truth values to its variables makes it false.

66
Q

Propositional solution

A

When we find a particular assignment of truth values that makes a compound proposition true, we have shown that it is satisfiable; such an assignment is called a solution of this particular satisfiability problem

67
Q

predicate

A

refers to a property that the subject of the statement can have

68
Q

propositional function

A

The statement P(x) is also said to be the value of the propositional function P at x.

Let P(x) denote the statement “x > 3.”

69
Q

preconditions

A

The statements that describe valid input are known

as preconditions

70
Q

postconditions.

A

the conditions that the output should satisfy when the program has run are known as postconditions.

71
Q

quantification

A

Quantification expresses the extent to which a predicate is true over a range of elements. In English, the words all, some, many, none, and few are used in quantifications.

72
Q

universal quantification

A

tells us that a predicate is true for every element under

consideration,

73
Q

existential quantification

A

tells us that there is one or more element under consideration for which the predicate is true

74
Q

predicate calculus

A

The area of logic that deals with predicates and quantifiers

75
Q

domain of discourse

A

Many mathematical statements assert that a property is true for all values of a variable in a particular domain, called the domain of discourse (or the universe of discourse), often just referred to as the domain

Ref: THE UNIVERSAL QUANTIFIER

76
Q

∀

A

universal quantifier “EVERY”

“P(x) for all values of x in the domain.”

The notation ∀xP(x) denotes the universal quantification of P(x). Here ∀ is called the universal quantifier.We read ∀xP(x) as “for all xP(x)” or “for every xP(x).” An element for which P(x) is false is called a counterexample of ∀xP(x).

77
Q

∃

A

existential quantification

universal quantifier “Exists”

“There exists an element x in the domain such that P(x).”

We use the notation ∃xP(x) for the existential quantification of P(x). Here ∃ is called the existential quantifier.

78
Q

“there is exactly one” and

“there is one and only one.”

A

uniqueness quantifier, denoted by ∃! or ∃1.

∃!x(x − 1 = 0),

79
Q

uniqueness quantifier

A

∃! or ∃1

80
Q

What are the Precedence of Quantifiers?

A

The quantifiers ∀ and ∃ have higher precedence than all logical operators from propositional calculus. For example, ∀xP(x) ∨ Q(x) is the disjunction of ∀xP(x) and Q(x). In other words, it means (∀xP(x)) ∨ Q(x) rather than ∀x(P(x) ∨ Q(x)).

81
Q

bound variable

A

When a quantifier is used on the variable x, we say that this occurrence of the variable is bound.

82
Q

free variable

A

An occurrence of a variable that is not bound by a quantifier or set equal to a particular value

83
Q

scope

A

The part of a logical expression to which a quantifier is applied is called the scope of this quantifier.

84
Q

Statements involving predicates and quantifiers are logically equivalent….

S ≡ T

A

if and only if they have the same truth value no matter which predicates are substituted into these statements and which domain of discourse is used for the variables in these propositional functions.

We use the notation S ≡ T to indicate that two statements S and T involving predicates and quantifiers are logically equivalent.

85
Q

De Morgan’s Laws for Quantifiers.

A

The rules for negations for quantifiers

When the domain of a predicate P(x) consists of n elements, where n is a positive integer greater than one, the rules for negating quantified statements are exactly the same as De Morgan’s laws discussed in Section 1.3. This is why these rules are called De Morgan’s laws for quantifiers.

86
Q
A
87
Q

Prolog facts

A

Prolog facts define predicates by specifying the elements that satisfy these predicates.

88
Q

Prolog rules

A

Prolog rules are used to define new predicates using those already defined by Prolog facts.

89
Q

nested quantifiers

A

where one quantifier is within the scope of another, such as

∀x∃y(x + y = 0).

90
Q
A
91
Q

it is sometimes helpful to think of me in terms of nested loops… What am I?

A

Nested Quantifiers

92
Q

Logical Equivalences and biconditional Statements

A
93
Q
A
94
Q
A
95
Q
A
96
Q
A

Discrete math (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions