Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [propositional-calculus]

Appropriate for questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions. Also for general questions about the propositional calculus itself, including its semantics and proof theory. Questions about other kinds of logic should use a different tag, such as (logic), (predicate-logic), or (first-order-logic).

0
votes
1answer
15 views

Converting from formula to clause

I'm trying to refresh myself on the subject. If φ= (L1 ∨...∨ Ln) whereL1,...,Ln are literals, then{L1, ..., Ln}is the clause associated to φ. How would I convert ¬(¬P ∨ Q) to a clause?
0
votes
1answer
32 views

Equivalence Between Law of Excluded Middle and Self-Implication

We know that $P \to Q$ is equivalent to $\neg P \lor Q$, as can be verified easily in truth table. Now suppose we have proof for self-implication below [the axiom system is Lukasiewicz's, with L1: $P ...
0
votes
1answer
23 views

How to determine a set of conclusions that can be derived from a set of premises?

Considering the following three premises. How is it possible to determine the set of conclusions that can be derived from the given set of premises. ...
2
votes
2answers
22 views

How to use the distributive law correctly in propositional logic?

Can someone explain how in propositional logic these are equivalent : A ∧ B ∧ (¬B ∨ ¬C) ≡ A ∧ B ∧ ¬C Because using the distributive law I would get: ...
0
votes
3answers
36 views

Using 0/1 instead of T/F in propositional logic. Is there any interest in doing so? ( either at the language level or at the metalogical level)

Is there any interest in using 0/1 instead of T/F in propositional logic? Does it allow things the T/F notation doesn't? Does it make easier or simplyfy in any way the exposition of logical theory?...
-1
votes
1answer
31 views

Is this Proof of (P→Q)→((Q→R)→(P→R)) based on Lukasiewicz Axiom System for CPL Correct?

Given Lukasiewicz axiom system for Classical Propositional Logic (CPL): (L1) α→(β→α) (L2) (α→(β→γ))→(α→β)→(α→γ) (L3) (¬α→¬β)→(β→α) and the usual Modus ...
0
votes
0answers
14 views

Proving the following statements are equivalent

How would I be able to show that the following are equivalenet: a) x |= =| y (b) For all Γ, Γ |= x <-> Γ |= y (c) For all Γ and γ, we have Γ union {x} |= γ <-> Γ union {y} |= γ I can prove a ...
0
votes
1answer
34 views

Prove by induction on structural complexity that the following set is complete

Consider the propositional language $L$ with denumerably many sentence letters $S_1,S_2,S_3,\ldots$ and the two connectives $\lnot,\lor$. Suppose that the set of sentences $\Gamma$ is a formal theory ...
0
votes
1answer
30 views

How to prove this propositional tautology using only axioms from Mendelson's “Introduction to Mathematical Logic”

The result I wish to prove is (A -> (B -> C)) -> (B -> (A -> C)) Firstly does this have a name? I've been calling it "Swapping Hypothesis". ...
2
votes
3answers
53 views

Natural deduction on exclusive OR

How do I formulate a natural deduction rule such that the conclusion is for example; a ∨ b (∨ being exclusive OR)
0
votes
3answers
63 views

Syntactic use of “ false” . After “ false” can I write anything I want? ( Not a semantic question on “ ex falso sequitur quodlibet”)

If the proof below proof is correct, I'd like to know what is the name of the rule involving " false" that is used here. This question is not on " ex falso sequitur quodlibet". From false follows ...
0
votes
1answer
43 views

How to transform a sequent notation to rule form?

I can write this proposition in sequent notation: $$(P\rightarrow Q)\rightarrow (\neg P \lor Q)$$ as this one in rule form (see here): $$\frac{(P\rightarrow Q)}{(\neg P \lor Q)}$$ But how can I ...
3
votes
3answers
60 views

Natural deduction proof: $C, (C \land D)↔F \vdash (D \land E) \to F$

I'm having trouble with proving C, (C Λ D) ↔ F |- (D Λ E) → F If it were $\lor$ instead of $\land$, then I would be able to do it. If I can prove that $(C ...
2
votes
1answer
32 views

How to derive ~ ( P&Q) from ~ P using natural deduction?

Certainly if P is false, (P&Q) cannot be true. But how to prove this using natural deduction? I'd propose as a direct proof the following derivation : (1) ~P ( Premise ) (2) ~P v ~Q ( ...
1
vote
2answers
31 views

Logical Equivalences with English Statements

Showing two statements $p$ and $q$ are logically equivalent is to show $p \Longleftrightarrow q$. I understand this, however I think when looking at english statements showing whether or not they are ...
0
votes
1answer
33 views

Usage of adjective and imperative in statement logic

I think I know how to form sentences in statement logic if it's an "if statement" like (A) and (B) below, but how do I express adjective like "not so easy" or imperative like "Choose X or Y", as shown ...
0
votes
1answer
67 views

How to prove $\vdash p\to\neg\neg p$ in this system?

I was asked to prove $\vdash p\to\neg\neg p$ in this system. Axioms: $(\mathcal A_1)\vdash p\to(q\to p)$ $(\mathcal A_2)\vdash (p\to(q\to r))\to((p\to q)\to (p\to r))$ $(\mathcal A_3)\vdash \...
-4
votes
0answers
36 views
4
votes
1answer
121 views

Why are there several axiom systems for propositional logic?

There is an axiom system that I found in Elliot Mendelson's, "Introduction to Mathematical Logic", p.27, and Theodore Sider's, "Logic for Philosophy", p.59: (A1) P->(Q->P) (A2) (P->(Q->P))->(P->Q)->(...
0
votes
0answers
14 views

Graph Coloring in Propositional Logic

Let G be a legally colored graph with k colors; this means that each two adjacent vertices have different colors, and the total number of colors in G is k. In addition, the edges of the graph are ...
0
votes
1answer
38 views

Is the “ contrapositive relation” rigorously symmetric? What is rigorously the contrapositive of : ~X --> ~ Y?

Is the relation " being the contrapositive of" really symmetric? I mean : the contrapositive of X --> Y is ~Y --> ~X. If the relation " being the contrapositive of " is symmetric, then I can say ...
-1
votes
1answer
36 views

Semantics of exclusive or

How do I get a description of $\text {XOR}$ (exclusive or) only using the operators $\wedge$, $\vee$, $\neg$, $\rightarrow$ And is it possible to prove the correctness of such description?
1
vote
3answers
67 views

Natural Deduction Proof: A ↔ B |- (C → A) → (C → B)

In an attempt to prove the formula, I tried setting a hypothesis C -> A like the following ...
1
vote
2answers
84 views

Prove that the set $\{((p\to q)\lor r),(p\lor(q\lor s))\}$ is satisfiable?

Am I using the correct logic in my proof below? Rewriting the first element in the set using Logical equivalence involving Conditional statement yields: $(\neg p\lor q)\lor r$ – this can be further ...
1
vote
2answers
61 views

Prove $(((p\land q)\to r)\land(p \to q))\to (p \to r)$ is satisfiable.

I'm trying to learn how to apply shortcuts of a truth table, and was wondering if the following is correct: Let $A=(p\land q)$ Let $B = (A \to r)$ Let $C=(p \to q)$ Let $D=(B\land C)$ Let $E=(p \...
0
votes
1answer
24 views

Classical Propositional Logic and Axioms

We define a new proof system N over the connectors: {∨,¬} For every α and β- 𝐴1: (𝛼 ∨ (𝛽 ∨ (¬𝛼))) (axiom) Deductions: 𝑀𝑃1: if we have 𝛼, 𝛽 then we can deduce (¬(¬(α∨β))) 𝑀𝑃2: if we have (...
0
votes
2answers
23 views

Disjunctive normal form of (¬(p → q) → (q ∧ ¬r))

I learning how to convert to disjunctive normal forms, I have the following, (¬(p → q) → (q ∧ ¬r)) I understand any p→q can be represented as (¬p)∨q, therefore ...
0
votes
3answers
40 views

Please explain (p ∧ q) --> r and what the correct method to work this out is

I understand P ∧ Q, being that both must be equivalent, ie True & True, or False and False. I understand P --> Q implies that if P is True we know what Q is and if Q is true then the result is ...
0
votes
1answer
17 views

logical equivalence proof using propositional algebra

i need help to show that (p⇔r)⇒(q⇔r) is equivalent to ∼[(∼p∨r)∧(p∨ ∼r)]∨[(∼q∨r)∧(q∨ ∼r) using propositional algebra. I did it using truth tables but i am struggling with propositional algebra.
0
votes
0answers
10 views

Symbolize using schemas, quantifiers and logical connective.

How can I symbolize the follow sentence: "not all integers numbers are positive" I tried to do this: if x∈ℤ and P(x)= x>0 (∃x)¬p(x) Thanks in advance.
0
votes
0answers
36 views

Substitution for propositional logic

In the propositional logic, let the string $(a_1, a_2, \cdots, a_n)$ be WFF. And exist natural numbers $i< j\in \{1,2 \cdots, n\}$ search that string $(a_i,a_{i+1}, \cdots , a_j )$ is also WFF. ...
0
votes
1answer
38 views

How can I deny the formula $(\exists x)(p(x)\vee(\forall y)h(y)) \leftrightarrow q $

Can anyone explain me how can I deny this propositional formula? $$(\exists x)(p(x)\vee(\forall y)h(y)) \;\leftrightarrow\; q $$ According to my textbook, the answer would be: $$(\forall x)(\sim p(x)...
1
vote
2answers
71 views
2
votes
1answer
27 views

Is a statement with a quantified function variable considered to be of second-order logic?

Here $\mathbb{N}=\left\{n\in\mathbb{Z}:0<n\right\},$ function parameter lists are delimited as $\left[\dots\right],$ and $\underline{\exists}$ means there exists exactly one. One way to state ...
0
votes
1answer
16 views

Proving inequality equivalence using propositional logic: stuck with redundancy at the end of the proof + circularity problem

I would like to prove formally that : ~ ( a is less than b or equal to b) is equivalent to ( a is strictly greater than b ). But I cannot get rid of a redundant conjoint at the end of the proof. ...
2
votes
1answer
40 views

Is the last variable of any implicational tautology also the last variable of one of its premises?

I'll define my terminology via the following BNF grammar for implicational logical expressions: <clause> ::= "(" ...
1
vote
2answers
94 views

Is it true that the statement: “ $\frac{1}{0}$=5 is false statement ” is unprovable statement?

I had a conversation on this site about some question, and a claim had been made by one of the users on this site that the truth value of this statement(" $\frac{1}{0}$=5 is false statement " ) is ...
0
votes
1answer
33 views

An example of a maximal consistent set?

I an doing old exams, and there is an exercise that asks to give an example of a maximal consistent set, and while i understand the definition, I cant seem to find or come up with an example.
2
votes
1answer
47 views

How do I write equivalent formulas using only $\to$ and $\bot$?

for following formulas in propositional logic, how do I write equivalent formulas using only logical symbols → and $\bot$: $\alpha$ $\land$ $\beta$ $\alpha$ $\lor$ $\beta$ $¬\alpha$ Is it ...
0
votes
2answers
56 views

What does the fact that “~P is equivalent to (P --> ~P) ” tell us about the nature of logical falsity?

After all, what does " false" mean in logic? Does this fact: "~P is equivalent to (P --> ~P) " deliver the essence of logical falsity? I mean , does this formula express the idea that being false,...
2
votes
2answers
23 views

Velleman - Conditional truth table justification

Velleman's logic in sentence 3 under figure 4 is confusing me. He is using lines two and four of the truth table to infer what Q of line 1 should be. But lines two and four assume P --> Q are true ...
1
vote
4answers
93 views

Natural deduction proof: $A \vee (B \wedge C) ├ (A \vee B) \wedge (A \vee C)$

I assume that I need to set a hypothesis somewhere in the process, but I don't know how. ...
1
vote
1answer
49 views

Natural deduction proof: C Ʌ D, C ↔ E, D ↔ F |- E Ʌ F

Originally, when I tried to solve this problem for the first time, my answer was like the following. ...
1
vote
2answers
33 views

Natural Deduction proof: C Ʌ D, C ↔ E |- (C V F) Ʌ (D V F) Ʌ (E V F)

This is one of the tasks that I'm working on in Logic class of a CS degree program at University. The teacher just said to me that my answer was wrong, but she never told me when I asked her where I ...
4
votes
2answers
67 views

Are “ replacement rules” and “ inference rules” ( in natural deduction) really two kinds of rules?

I think the distinction, in natural deduction systems, between " inference rules" and " replacement rules" is standard. ( For example, Bergmann, The Logic Book). Is " replacement rule" anything ...
0
votes
1answer
45 views

Is there a general and mechanical method to solve algebra of sets (or alg.of propositions) equations?

In some simple cases it seems possible to solve for X a set equation. For example, if I am given : X Inter U = U , and knowing the law according to which S Inter U = S for any set S, I can find ...
1
vote
0answers
55 views

“Truth set” approach to validity and logical consequence: how does it relate to the standard approach? what are the possible drawbacks?

References : I think the " truth set approach" to validity and logical consequence can be linked to the name of R. Carnap ( who defines L-truth and L-implication in this way in his Introduction to ...
0
votes
0answers
6 views

Prove that $\hat{\alpha}$ is a base of $2^\mathbb{P}$

Let it be $\mathbb{P}$ a set of propositional letters and $\phi$ a set of formulas generated by $\mathbb{P}$. Consider the space $2^{\mathbb{P}}$ with the product topology, and define for every ...
2
votes
1answer
55 views

If every truth assignment satisfies some wff, some finite disjunction is a tautology

Let $X_1,X_2,X_3,...$ be well formed formulas. If for every truth assignment $v$ there exists $n$ with $X_n$ satisfied by $v$, show there exists $n$ with $X_1\lor...\lor X_n$ a tautology. We can ...
2
votes
1answer
33 views

Help me with this propositional logic demonstration

This is a simple propositional logic demonstration. I’d appreciate your help. I don’t know if my answer is correct, but the textbook used another demonstration. The question $T \vee R$ $(T \vee R) \...