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)

36
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
3k 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 ...
5
votes
4answers
334 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$?
8
votes
2answers
971 views

Does 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: $$ \lnot (p \land q) \iff \lnot p ...
4
votes
3answers
550 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)$. ...
1
vote
1answer
55 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
136 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) ...
4
votes
2answers
332 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
48 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
1k 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
234 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
160 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 ...
7
votes
2answers
8k 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
5answers
577 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
2answers
75 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 ...
1
vote
2answers
80 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 ...
15
votes
5answers
490 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 ...
17
votes
4answers
332 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 ...
4
votes
7answers
202 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
190 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
383 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
292 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
152 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
891 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
334 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
126 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
6answers
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
118 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
234 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
357 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
74 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
4answers
196 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
53 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
191 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
598 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
181 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
1answer
40 views

formal proof - logic

I am trying to prove the following, using natural deduction: $$p\wedge q\Leftrightarrow p \vdash p \Rightarrow q$$ with the following but i seem to get stuck. I know i have to prove $q$, but am not ...
2
votes
2answers
201 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 ...
2
votes
3answers
110 views

deducing $\lnot B \implies \lnot A$ from $A \implies B$

One way how to prove a statement of the form $A \implies B$ is to presume that $A$ is true and deduce $B$. Lets have $A \implies B$ and lets assume that $\text{not}~B$ is true. $A$ is true or it is ...
2
votes
1answer
197 views

Proof of the distributive law in implication

I am doing a practice exam and in it is the following question: Show without truth tables that the following logical equivalence holds: $$(p → q) ∧ (p → r) ≡ p → (q ∧ r)$$ I attempted to substitute ...
2
votes
2answers
124 views

How to prove that $(A \lor B) \land (\lnot A \lor B) = B$

I know this is fairly basic, and I understand that it becomes $$ \begin{align} (A \land \lnot A) \lor B \\ F \lor B \\ B \end{align} $$ However, I can't work out how to prove that it becomes that ...
2
votes
3answers
241 views

Writing Propositions With Propositional Variables

The puzzle I am working on is: "Let $p$, $q$, and $r$ be the propositions $p$: Grizzly bears have been seen in the area. $q$: Hiking is safe on the trail. $r$: Berries are ripe along the trail. ...
2
votes
1answer
104 views

Finding a logical expression (under some constrains) s.t. it is equivalent to another one

In this question, it was made clear, when $\bullet$ some statement $A$ is stronger than another statement $B$, namely if $A\Rightarrow B$ holds; and when the statement $A$ is weaker than another ...
2
votes
1answer
2k views

How to prove the distributive property without using truth tables?

I did it with using truth tables but I am inquisitive about how to proof the distributive property without using truth tables (i.e using the other rules of replacement or inference). $$ (P \land (Q ...
1
vote
2answers
323 views

Proving ${\sim p}\mid{\sim q}$ implies ${\sim}(p \mathbin\& q)$ using Fitch

I am struggling with proving something in Fitch. How can I prove from the premise ~p | ~q , that ~(p & q). Any ideas on how I should proceed?
1
vote
2answers
132 views

Simple proof theory - Propositional Logic

When addressing the questions, which are featured below, I use the following definition and two lemmas. Definition: $\phi$ is a tautology if $[[\phi]]_{v}=1$ for all valuations $v$. Moreover, ...