Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.

learn more… | top users | synonyms (1)

37
votes
16answers
3k views

In classical logic, why is$ (p\Rightarrow q)$ True if both p and q are False?

I am studying entailment in classical first-order logic. The Truth Table we have been presented with for the statement $(p \Rightarrow q)\;$ (a.k.a. '$p$ implies $q$') is: ...
4
votes
4answers
4k views

What is the name of the logical puzzle, where one always lies and another always tells the truth?

So i was solving exercises in propositional logic lately and stumbled upon a puzzle, that goes like this: Each inhabitant of a remote village always tells the truth or always lies. A villager will ...
10
votes
7answers
7k views

Not understanding this row of truth table for logical implication

Provided we have this truth table where "$p\implies q$" means "if $p$ then $q$": $$\begin{array}{|c|c|c|} \hline p&q&p\implies q\\ \hline T&T&T\\ T&F&F\\ F&T&T\\ ...
6
votes
4answers
363 views

Equivalence of $a \rightarrow b$ and $\lnot a \vee b$

Is there a proof for the logical equivalence of $a \rightarrow b$ and $\lnot a \vee b$?
11
votes
2answers
1k views

Do De Morgan's laws hold in propositional intuitionistic logic?

In Wikipedia page on intuitionistic logic, it is stated that excluded middle and double negation elimination are not axioms. Does this mean that De Morgan's laws, stated $$ \lnot (p \land q) \iff ...
5
votes
4answers
601 views

What is a constructive proof of $\lnot\lnot(P\vee\lnot P)$?

Glivenko's theorem says that $\lnot\lnot P$ is a theorem of intuitionistic logic whenever $P$ is a theorem of classical logic. Is it closely related to the so-called Gödel–Gentzen negative translation ...
7
votes
5answers
1k views

Help to understand material implication

This question comes from from my algebra paper: $(p \rightarrow q)$ is logically equivalent to ... (then four options are given). The module states that the correct option is $(\sim p \lor q)$. ...
4
votes
3answers
149 views

Natural Deduction Tautology

I'm trying to prove the following tautologies: \begin{align} & ⊢ (A \to (B \to A)) \\ & ⊢ ((A \to B) \to A) \to A \end{align} For the first one, what I did was: $A$ assumption $B$ ...
2
votes
1answer
206 views

How do I Prove the Theorems Needed for “The Deduction Meta-Theorem” from CδCpqCpδq?

I use Polish notation. δ stands for a variable function (or functor) of one argument. A section of Lukasiewicz's book on Aristotle's syllogistic from the modern point of view reads: "I should like ...
1
vote
1answer
183 views

How to prove Lemma 2.12 of Mendelson without Deduction Theorem

My question refers to Bourbaki's axiom system in Nicolas Bourbaki, Théorie des ensembles (1970). [page I.25] : $(P \lor P) \supset P$ --- (Taut) $Q \supset (P \lor Q)$ --- (Add) $(P \lor Q) ...
1
vote
1answer
58 views

How to find if a valuation satisfies a statement?

I'm working on a task which i'm a bit stuck at. I need to decide whether the statements are true or fale. F stands for the statement logical formulas, and also if the claim is true I need to give a ...
0
votes
1answer
89 views

How make equivalent transformations?

Please, help me make equivalent transformations with this formula (A∨C→B)(A→C)(¬B→¬A∧C)(¬A→(C→B))(B→¬C→¬A). Thanks.
4
votes
2answers
341 views

How Many Theorems (Tautologies) Exist of 5, 6, 7, 8, and 9 Letters?

Suppose we only have the material conditional C and logical negation N for a system of propositional calculus, with only variables and no constants in any formula. Suppose that formulas like Cpq ...
0
votes
1answer
53 views

Does $\neg(x > y)$ imply that $y \geq x$?

Given any arbitrary binary relation $\geq$ defined on some set $S$, we define a new binary relation $>$ on $S$ by: $$ x > y \quad\text{iff}\quad (x \geq y) \wedge \neg(y \geq x) $$ In accordance ...
5
votes
3answers
2k views

Express logic puzzles with proposition calculus notation

I’m trying to solve a logic puzzle that goes like this: The police have three suspects for the murder of Mr. Cooper: Mr. Smith, Mr. Jones, and Mr. Williams. Smith, Jones, and Williams each declare ...
3
votes
5answers
400 views

Intuition of implication in propositional logic

So, in all the books on propositional logic, I feel unsatisfied with the "intuition" about the meaning of the implication connective. I completely understand how the mechanics work via truth tables, ...
2
votes
3answers
177 views

Logical Equivalence and Corresponding English Statements

Consider the statement, "If it is Tuesday, then it is raining"; in propositional logic, the statement would read as, "$p \implies q$." Now, in accordance with the rules and definitions prescribed in ...
1
vote
1answer
80 views

In Fitch, is a symbol not in a specified language automatically free?

In Fitch proofs where no language has been specified, we (at least seem to) treat lines that have the form $$p(x)$$ to mean that $x$ "can be anything". That is they are equivalent to $$\forall ...
8
votes
2answers
9k views

How to convert to conjunctive normal form?

If i have a formula: $((a \wedge b) \vee (q \wedge r )) \vee z$, am I right in thinking the CNF for this formula would be $(a\vee q \vee r \vee z) \wedge (b \vee q \vee r \vee z) $? Or is there some ...
3
votes
3answers
109 views

A question about Implicational Propositional Calculus

My question is motivated by a previous post about Implicational calculus Having showed that Mendelson (A1) and (A2) axioms plus Peirce's law are a complete axiom set for implicational fragment of ...
3
votes
5answers
643 views

Tautology, Contradiction, or a satisfiable equation? Confusion about implication.

I'm having some trouble with a homework question. I have the following $ P \rightarrow \neg P$ This looks like a contradiction to me. This should never be true! Yet, if I transform it using $p ...
2
votes
5answers
87 views

Showing that $\lnot Q \lor (\lnot Q \land R) = \lnot Q$ without a truth table

I've done a truth table after reducing it to this and it seems to be equal to $\neg Q$: $$\lnot Q \lor (\lnot Q \land R) = \lnot Q$$ But when I try to show it without a truth table (with just ...
1
vote
2answers
82 views

Deriving $\neg R$ from $\{R↔(R∨(P∧¬P)), R↔¬P, ¬P→(P↔(Q→Q)), P→Q\}$

Give a derivation of $\neg R$ from the following premises: $$\{R\leftrightarrow(R\lor(P\land \neg P)), R\leftrightarrow\neg P, \neg P\to(P\leftrightarrow(Q\to Q)), P\to Q\}$$ using the ...
16
votes
5answers
512 views

If both $P$ and $Q$ are true , how can I tell that $P$ implies $Q$?

I am trying to understand the fundamentals of mathematical logic in order to be able to study discrete mathematics and computer science soon. I have a big problem understanding Implication. I ...
18
votes
4answers
382 views

Associativity of $\iff$

In this answer, user18921 wrote that the $\iff$ operation is associative, in the sense that $(A\iff B)\iff C$ $A\iff (B\iff C)$ are equivalent statements. One can brute-force a proof fairly ...
6
votes
1answer
233 views

distribution of categorical product (conjunction) over coproduct (disjunction)

In the classical and intuitionistic propositional calculi, it is straightforward, using natural deduction, to derive $((A \land C) \lor (B \land C))$ from $(A \lor B) \land C$: Assume $(A \lor B) ...
4
votes
7answers
224 views

Conditional Statements: “only if”

For some reason, be it some bad habit or something else, I can not understand why the statement "p only if q" would translate into p implies q. For instance, I have the statement "Samir will attend ...
2
votes
2answers
200 views

Propositional Calculus and “Lazy evaluation”?

I want to formalize a system, and currently I don't know, if I can use propositional calculus in my case. At first, I though that I need a simple conjunction. $A \wedge B$ However, there is a ...
7
votes
3answers
465 views

Why Peirce's law implies law of excluded middle?

Why if in a formal system the Peirce's law $((P\rightarrow Q)\rightarrow P) \rightarrow P$ is true, the law of excluded middle $P \lor \neg P$ is true too?
5
votes
2answers
1k views

What's the difference between a negation and a contrapositive?

What's the difference between a negation and a contrapositive? I keep mixing them up, but it seems that a contrapositive is a negation where the terms' order is changed and where there is an imply ...
5
votes
3answers
300 views

How complicated is the set of tautologies?

Consider the set $\mathcal T$ of all tautologies in the propositional calculus in which the only operators allowed are $\to$ and $\neg$, and involving only the two variables $x$ and $y$. How ...
2
votes
2answers
167 views

Proving and Modeling Logical Consistence

Suppose I have a finite list of logical statements (would these be called axioms?) and for the sake of discussion say that there are 6 such statements. All statements are in the form of propositional ...
2
votes
1answer
1k views

Relation between XOR and Symmetric difference

I noticed that XOR and symmetric difference use the same symbol, $\oplus$. They also seem to have a similar structure: XOR: $(\neg P\wedge Q)\vee(P\wedge \neg Q)$ Symmetric Difference: $(A\cap ...
6
votes
7answers
350 views

Intuition behind “If P then Q” = “Q or Not P ”

I understand with truth tables the Conditional Law: $[P \Longrightarrow Q] \equiv [\lnot P \vee Q]$. However, what's the intuition or a natural motivation? Source 1, all but intuitive, now appears as ...
6
votes
3answers
137 views

Equivalence relation using tableaux

How can I prove that two formulae are equivalent using analytic tableaux? For example, how can I prove the following theorem? $$ (p \rightarrow q) \equiv (\neg q \rightarrow \neg p)$$
6
votes
7answers
3k views

Associativity of logical connectives

According to the precedence of logical connectives, operator $\rightarrow$ gets higher precedence than $\leftrightarrow$ operator. But what about associativity of $\rightarrow$ operator? The implies ...
5
votes
3answers
125 views

Can Peirce's Law be proven without contradiction?

Good evening, I heard the proof by contradiction is required for Peirce's law. AFAIK, truth tables are not related directly to proofs by contradiction, and if of an operation $\text {op}$ we have a ...
5
votes
1answer
247 views

What are a list of helpful boolean identities for solving boolean functions?

For instance, things like $P \Leftrightarrow Q \equiv (P \Rightarrow Q) \land (Q \Rightarrow P)$ is a very helpful formula to know, as is $P \Rightarrow Q \equiv \lnot P \lor Q$ is another helpful ...
4
votes
2answers
183 views

Natural deduction: $(\neg q \to\neg p)\vdash(p\to q)$ without Modus Tollens

Can anyone help me to obtain this result in natural deduction, without using modus tollens: $$(\neg q \to \neg p) \vdash ( p \to q)$$
4
votes
2answers
369 views

Disjunction in Intuitionistic Logic, what about $((P \to U \lor V) \to Z)$

I wonder whether the following holds in intuitionistic logic: $$((P \to U \lor V) \to Z) \leftrightarrow ((P \to U) \to Z) \land ((P \to V) \to Z)$$ For disjunction I assume the following two rules: ...
3
votes
2answers
108 views

Model-theory and Proof-theory in Propositional Logic

I'm trying to link results of model theory and proof-theory in propositional language. Here i will use $\models$ to denote logical consequence, in the model-theory sense. Being $x,y$ two formulas of ...
3
votes
3answers
233 views

Proof of $A \lor B, \lnot A\models B$ with natural deduction

Prove that: $A \lor B, \lnot A\models B$ Looks easy but im stuck, and i dont know if to start with an OR elimination or with NOT introduction. Also, different books/texts/etc about Natural ...
3
votes
4answers
211 views

Proving $q\Rightarrow r \models (p\land q) \Rightarrow (p \land r)$ using only natural deduction.

I'm trying to prove $$q\Rightarrow r \models (p\land q) \Rightarrow (p \land r)$$ using only the natural deduction rules in this handout. Any hints? I am not allowed to do transformational stuff, ...
3
votes
0answers
58 views

Boolean combinatorics

Every finite Boolean algebra has a "middle layer", corresponding to the subsets of size $n/2$ (when looking at the algebra of subsets of $[n]$) or to a set of formulas including $p_i, \neg p_i, p_i ...
3
votes
2answers
216 views

Why implication ($\phi x \Rightarrow \psi x$) is always true according to Russell?

In the chapter XV of the Intro. to Philosophical Math, Russell says that every propositional function (PF) of the form: "$\phi x$ implies $\psi x$" is always true. Russell gives the following ...
3
votes
2answers
733 views

Formation sequence for a logic formula

I will start with some definitions from An Introduction to Mathematical Logic and Type Theory: To Truth through Proof by Peter B. Andrews then give the exercise that I am working along with my attempt ...
3
votes
1answer
186 views

Question about maximal consistency

Let $\sigma$ be a consistent set of propositions such that for every set $\gamma$, either $\sigma$ is proofwise stronger than $\gamma$ that is {$\alpha : \sigma \vdash \alpha$} $\supseteq$ {$\alpha ...
2
votes
3answers
54 views

If $(A \vee B) \wedge (¬B \vee C)$ is true, then $(A \vee C)$ must be true … can I argue that?

If $(A \vee B) \wedge (¬B \vee C)$ is true, then $(A \vee C)$ must be true ... can I argue that? I don't see how I can argue that $(A \vee C)$ must be true because can't we have $(T \vee T) ...
2
votes
3answers
378 views

Deduction Theorem + Modus Ponens + What = Implicational Propositional Calculus?

Implicational propositional calculus is a system of propositional calculus in which implication is the only logical connective, and all other connectives are defined with respect implication and a ...