Brainscape's Knowledge GenomeTM

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


See full index

COMP 230 > Propositional Logic as a Calculus > Flashcards

Propositional Logic as a Calculus Flashcards

1. Natural Deduction Calculus 2. Axiomatic Calculus 3. GEB Calculus

1
Q

When is an inference valid?

A

Whenever it is impossible for the premises to be true and the conclusion to be false, the inference is valid

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

What are two ways propositional logic is used?

A
  1. Express complex statements (trees)
  2. Conclude or infer certain statements from others (calculus)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Is entailment semantic or syntactic

A

Semantic

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

What is the notion of validity?

A

Semantic notion, since it refers to the meaning of wffs - in terms of its truth values.

Can be used to define when a wff A (conclusion) follows from the set of wffs (premises):
A wff A is a (semantic) consequence of a set of wffs A0, …, An (or A0, …, An entails A) if it is impossible that A0, …, An are all true and A is false at the same time. Write as:

A0, …, An ⊨ A

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

How can wffs be defined as a notion of validity?

A

A wff A is a (semantic) consequence of a set of wffs A0, …, An (or A0, …, An entails A) if it is impossible that A0, …, An are all true and A is false at the same time. Write as:

A0, …, An ⊨ A

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

How to know if the premises are true and the conclusion is false?

A

Try all the possible truth assignment values. Find the row were all the premises are true then look at the conclusion.

A0, …, An ⊨ A
T ⊨ F

Therefore, must be decidable and have a decision prodecure

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

What happens when the conclusion A in entailment (A0, …, An ⊨ A) is always true regardsless of the truth value assignment?

A

Then, it is a semantic consequence of the empty set, just written as ⊨ A

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

What is the difference between entailment and implication?

A

Truth Conditions Similar
Entialment: (⊨)
* Meta-langugae (How formulas relate to other formulas)
* Different kind of truth: taking about relation
* Semantic

Implication: (⊃)
* Formulas (language) and Object language: (Formula. Ex: (A ∧ B))
* Bivalence (true or false)
* Syntax

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

Natural Deduction Calculus

What is natural deduction calculus?

A

System allows to do proofs for natural logic + inference rules

Inference rules: written with premises above the horizontal line and a conlcusion below it

Read from top to bottom: formally deduce the conclusion from the premises.

Sets of formulas connected by inference rules

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

Natural Deduction Calculus

Modus Ponens:

A

That B follows from A ⊃ B expressed as a syntactic rule of inference: MODUS PONENS

Read from top to bottom: formally deduce the conclusion

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

Natural Deduction Calculus

What are the rules for conjuction

And-elimination and And-introduction

A

Allows the elimination of a conjuction symbol, thus “∧-Elim”.

Alternative, introduce a conjuction symbol, we need both A and B as premises.

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

Natural Deduction Calculus

Define a derivation or proof in NDC?

A

By applying one+ inference rules we obtain a derivation or proof in the form of a tree.

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

Natural Deduction Calculus

Natural Deduction Proof 1:
(A ∧ B ⊢ B ∧ A)

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

Meaning “⊢”:

A

Symbol for LOGICAL THEOREMS:

Means that Q is derivable from P in the system. Consistent with its use for derivability, a “⊢” followed by an expression without anything preceding it denotes a theorem, which is to say that the expression can be derived from the rules using an empty set of axioms.

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

Natural Deduction Calculus

How to write the conclusion of the tree in NDC?

A

Formulas top of a derivation tree are the premises (used multiple times in a derivation) and the conclusion is at the bottom of the tree.

If A is obtained by a derivation from the premises A0, …, An, we have:
A0, …, An ⊢ A

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

Natural Deduction Calculus

What is Implication Elimination?

A

Modus ponens eliminates an implication formula: “⊃-Elim”

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

Is (A ∧ B) and (B ∧ A) logically equivalent?

A

(A ∧ B) ≠ (B ∧ A)

Different formulas so not logically equivalent

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

Natural Deduction Calculus

Implication introduction:

A

Allows us to infer A ⊃ B, from a proof B from the assumption A.
* Original assumption of A becomes internalized in colcusion so it is dischanged from proof (expressed by square brackets around assumption [A])
* Discharged assumption does not count as an assumption in the proof and cannot be used fruther down the proof tree.

Open Assumptions: Assumptions that are not dischanged

Appying “⊃-Intro” rule to derivation in proof 1, both occurances of the assumption dischanged because they both appear above the formula tree.

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

Natural Deduction Calculus

What are open and closed assumptions?

A

Allows us to infer A ⊃ B, from a proof B from the assumption A.
* Original assumption of A becomes internalized in colcusion so it is dischanged from proof (expressed by square brackets around assumption [A])
* Discharged assumption does not count as an assumption in the proof and cannot be used fruther down the proof tree.

Open Assumptions: Assumptions that are not dischanged

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

Natural Deduction Calculus

What is the special case for implication elimination?

A

If “B” is true, then A= irrelevent.

Preserves truth

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

Natural Deduction Calculus

Derive A ⊃ (B ⊃ A) with no open assumptions:

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

What is logical theorem?

A

Only derived from logic, not other theorems

Formulas like A ⊃(A ⊃ B) which can only be proved in derivations without open assumptions are called logical theorems.

Use symbol (⊢)

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

Natural Deduction Calculus

Introduction Rules for Disjunction:

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

Natural Deduction Calculus

Elimination Rule for disjunction:

A

This is a structure for proof by cases

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

Natural Deduction Calculus

Formula for introduction and elimination rules for negation:

A

Symbol: “⊥” (propostion tha is always false - a contradiction)

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

Natural Deduction Calculus

Is a (A) = (~~ A)

A

Not the same formula (syntax)

Though they are logically equivalent (semantics)

In the GEB system, the “~~ “ can be cancelled out

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

Natural Deduction Calculus

Derive B ∨ D from the assumptions A V C, A ⊃ B, and C ⊃ D.

Argument form of ‘dilemma’

Proof 3:

A
28
Q

Natural Deduction Calculus

Prove:
A V ~ A (tertium non datur; law of the excluded middle) is a theorem.

Proof 4:

A
29
Q

Axiomatic Calculus

What is Axiomatic Calculus?

A

Proof system
Good system - only one rule (modus ponens) and axioms

  1. Inference Rule: From A and A ⊃ B infer B (modus ponens)
  2. Substitution Rule: Any wff can be substitued for the metalofical variables A, B, and C

Natural Deduction calculus has many rules of inference

30
Q

Define proof (for calculus):

A

Sequence of formulas (wff axioms / obtained through inference rules)

31
Q

Axiomatic Calculus

Why is it called “axiomatic”?

A

it consists of following 10 axiom schemata which can serve as a starting points for derivations

32
Q

Axiomatic Calculus

How does the system allow for a concise recursive definition of proofs?

A

A proof of a wff A from a sets of assumptions A0, …, An is a sequence of wffs, such that each of them is either

a) an assumption, or
b) an instantiation (the result of applying a substitution) of one of the axiom schemata, or
c) obtained from a previous wffs in the sequence by modus ponens

33
Q

Axiomatic Calculus

Show: A ⊃ A ⊢B ⊃ (A ⊃ A)

A
34
Q

Axiomatic Calculus

Show: A ⊃ B, B ⊃ C ⊢ A ⊃ C

Proof 3:

A
35
Q

Axiomatic Calculus

Show: ⊢ (A ∧ ~ A) ⊃ B

Proof #4

A
36
Q

GEB System

Joining and Separation Rule

A
37
Q

GEB System

Double-tilde Rule:

A

The string ‘~~ ‘ can be deleted from any theorem. Also inserted into any theorem

38
Q

GEB System

Fantasy Rule:

A

If B can be derived when A is assumed in a theorem, then (A ⊃ B) is a theorem

⊃-Introduction

39
Q

GEB system

Carry-over Rule:

A

Inside a fantasy, any theorem from reality one level higher can be brought in and used

40
Q

GEB system

Rule of Detachment:

A

If A and (A ⊃ B) are theorems, then B is a theorem

41
Q

GEB System

Contrapositive Rule, De Morgan’s Rule, and Switcheroo Rule

A
42
Q

GEB System

Proof 1: (A ∧ B) ⊃ (B ∧ A)

A
43
Q

What are the semantic and syntactical notions of consequence?

A
44
Q

What is meta-logic?

A

Used when systems are isomorphic (such as the different calculus systems)

45
Q

What are the equivalence of proof systems?

A

System of Natural deduction, axiomatic proof system, and GEB systems prove the same theorems

46
Q

How to show the equivalence of ND with axiomatic calculus:

A

a. Use the ND system to derive all the axioms of the axiomatic system
b. Use the axiomatic system to justify all the rules of the ND system.

47
Q

What is the relation between the semantic method of proof and the syntactic one?

A
48
Q

Natural Deduction Calculus

(P → R) ∧ (Q → R) ⊢ (P ∨ Q) → R

A
49
Q

Natural Deduction Calculus

(P ∧ Q) → R ⊢ P → (Q → R)

A
50
Q

Natural Deduction Calculus

P ∧ Q → Q ∧ P

A
51
Q

Natural Deduction Calculus

P ∧ Q → Q ∧ P

A
52
Q

Natural Deduction Calculus

P → Q, Q → R ⊢ P → R

A
53
Q

Natural Deduction Calculus

P ∧ Q, P → R, Q → S ⊢ R ∧ S

A
54
Q

Natural Deduction Calculus

P ∨ Q, ~Q ⊢ P

A
55
Q

Natural Deduction Calculus

~P → P ⊃ Q

A
56
Q

Homework 03:

Show that B V (A ⊃ A) is a tautology

A
57
Q

Homework 03:

Prove B V (A ⊃ A) through Natural Deduction Calculus

A
58
Q

Homework 03:

Prove B V (A ⊃ A) using the axiomatic calculus:

A
59
Q

Homework 03:

Prove B V (A ⊃ A) using the GEB calculus:

A
60
Q

Homework 03 - Handout 2b, Exercise 8

P1, P2 |= ∼P1 ⊃ P2) ⊃ (P2 ⊃ P1)?

A
61
Q

Homework 03 - Handout 2b, Exercise 10

Answer the question:

A
62
Q

Homework 03 - Handout 2b, Exercise 15

A proof of P ⊃ (Q ⊃ (P ∧ Q)) in Natural Deduction:

A
63
Q

Homework 03

Explain formal language:

A

To explain these ideas to a friend, you first need to tell them that we’re discussing a formal language called Propositional Logic. This formal language, as opposed to a natural language like English, is designed to represent and reason about basic logical reasoning. We define our language in two parts: Firstly, with a vocabulary (alphabet) and a grammar (the syntax), and secondly with an unambiguous interpretation (semantics) of its grammatical sentences (well-formed formulas). You should also point out that the grammar of this language has a very simple (recursive) structure.

64
Q

Homework 03:

Difference between semantic entailment and provability:

A

The difference between semantic entailment ( |=) and provability ( ⊢). Both notions describe a relationship of consequence between a set of premises (Γ) and a conclusion A, but semantic entailment corresponds to the interpretation of consequence in Propositional Logic, whereas provability corresponds to a method that establishes consequence in Propositional Logic on the basis of sentence structure. If we say that Γ entails A, we mean that A is a consequence of Γ according to the unique interpretation that is part of the language of Propositional Logic, whereas if we say that Γ proves A, we mean that a method that examines the structure of the sentences in Γ and A tells us that A is a consequence of Γ.

65
Q

Homework 03

What it means for Propositional Logic to be sound

A

What it means for Propositional Logic to be sound.

If whenever the provability test says “Yes” the entailment test says “Yes” then Propositional Logic is sound. This means that the method that examines the structure of Γ and A only tells us that there is a logical consequence between A and Γ if there really is one according to the interpretation of Propositional Logic. However, it is possible that the method will reject some Γ, A (i. e., respond with a “No”) even though A is a consequence of Γ according to the interpretation given to Propositional Logic. In other words, soundness tells us that the syntactic method identifies only those consequence relationships that agree with PL semantics, but not necessarily all of them.

So the fact that propositional logic is both sound and complete means that, given a set of premises Γ and a conclusion A, the result of a Natural Deduction (or axiomatic) derivation Γ ` A and the result of a truth table test for Γ |= A are always in agreement.

In other words, the semantic and syntactic notions of consequence are equivalent, and we can thus use one or the other interchangeably

66
Q

Homework 03

What it means for Propositional Logic to be complete

A

What it means for Propositional Logic to be complete.

Completeness is the opposite relationship. It tells us that the syntactic method identifies all of the consequence relationships that agree with PL semantics, but it might also pick out some bad ones, too. Put another way, if whenever our entailment test says “Yes” the provability test says “Yes” then Propositional Logic is complete. However, it is possible that the provability test will say “Yes” to some Γ and A whereas the entailment test will reject Γ and A.

So the fact that propositional logic is both sound and complete means that, given a set of premises Γ and a conclusion A, the result of a Natural Deduction (or axiomatic) derivation Γ ` A and the result of a truth table test for Γ |= A are always in agreement.

In other words, the semantic and syntactic notions of consequence are equivalent, and we can thus use one or the other interchangeably

67
Q

P → Q , Q → R ⊢ P → (Q ∧ R)

A

COMP 230 (23 decks)

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