Logic Flashcards Preview

2. Fundamentals of Maths (CSC 1026) > Logic > Flashcards

Flashcards in Logic Deck (22)
Loading flashcards...
1

What does logic deal with?

Whether statements are true or false + chains of reasoning which enable us to decide this. Work with boolean + truth tables + de Morgan's laws.

2

What are the symbols for and, or not?

and = ^. Or = v. Not = ¬.

3

What is the opposite of A^B?

¬A v ¬B. We find opposite by negating variable + swapping and/or symbols.

4

When is A ⇒ B false?

When A is true and B is false.

5

What is the contrapositive of A ⇒ B?

¬B ⇒ ¬A. They mean the same thing.

6

If you chain logical deductions together, how do you know when it's always true?

If the truth table is true in every scenario.

7

What is forward chaining?

Search from initial conditions to goal. Start with what we know. Could end up with lots of intermediate deductions that aren't needed for final answer.

8

What is backward chaining?

From goal back to initial conditions. Start with what we want to know. Can end up with lots of questions which we don't need an answer to.

9

What is propositional logic?

Logic used when something must be proved/disproved (proposition)

10

What is predicate logic?

When we need to find out more about unknown variable before we can prove/disprove it. It tells you something about the subject and so is a Boolean function applied to 1 or more variables.

11

What happens when you add values to a predicate?

It becomes a proposition.

12

What is the domain/universe of discourse?

Set of values which can be assigned to predicate variable.

13

What are the quantifiers?

For all (∀) or there exists (∃) to indicate num of values for which predicate is true. For all shows all values are true. There exists shows at least one (possibly all) values are true for predicate. E.g. ∀x∈D .P(x) (for all possible values of x in domain D, P(x) is true.

14

What is a counterexample?

With for all, there must be at least 1case where p(x) is false so ¬( ∀x∈D.P(x)) = ∃x∈D.¬P(x) AND ¬( ∃x∈D .P(x) ) = ∀x∈D.¬P(x). You flip rule + negate predicate. Domain not affected.

15

How do you prove 'there exists'?

You just need 1 example.

16

What is the lovers relationship?

Use 2 different quantifiers. Let L(a,b) be ‘a loves b’. Can use statements such as ∀x∈D. ∃y∈D.L(y,x) meaning everyone is loved by someone

17

What is the difference between a finite and infinite sequence?

Finite sequences we know length and can specify each term's index, we limit domain to num of terms in sequence. Strong parallel between ∀i + for loops for arrays. With infinite, we don't know how many there are but if there's a pattern we can make a conjecture about subsequent terms so can make a predicate rule for this.

18

What is the difference between an ordered and a sorted sequence?

A sequence is already ordered but sorted means in asc/desc order.

19

What is the Fibonacci sequence?

Addition of previous 2 numbers in sequence but have to declare first 2 values as don’t have 2 previous values.

20

How do we concatenate sequences?

Tie symbol means concatenation, join 2 sequences together (⌢).

21

How do we declare a subsequence in predicate logic?

Use subseq(S,T) to state if something is a subsequence, but not in VDMLab. To ref subsequence, use S(starti,…,endi)

22

How can we use predicate logic for sequences of word?

Create predicate that detects repeated words e.g. ∃i∈{2,…,len(S)}.S(i)=S(i-1). If word spelt wrong, check if every word is in dictionary. E.g. ∀I ∈{1,…,len(S)}. ∃J ∈{1,…,len(D)}.S(i)=D(j).