# 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).

4,104 questions
Filter by
Sorted by
Tagged with
36 views

### Negation of “Either X is true, or Y is true, but not both”

Negation of "Either X is true, or Y is true, but not both" My attempt: If seems that let X be true and Y be true, not X for X is false and not Y for Y is false. In order for the above statement to ...
40 views

### What is the intuition behind the formula $p \leftrightarrow (q \leftrightarrow (r \leftrightarrow …))$?

I cooked up the formula $p \leftrightarrow (q \leftrightarrow (r \leftrightarrow ...))$ and naively thought it is a sort of "equivalence" relation. It turns out I am wrong. Suppose you have four ...
35 views

### Is there a Hilbert-style Axiom system for Classical Propositional Logic where formulae are in negation normal form?

The wiki page (https://en.wikipedia.org/wiki/List_of_Hilbert_systems) has a list of various axiom systems for classical propositional logic (CPL), however, the page omits mention of an axiomatisation ...
78 views

### Natural deduction has me stuck

I have been trying to break down these two formula correctly using natural deduction, and now I am stuck and confused. Below there is my attempt to derive the propositional logic consequences. I need ...
20 views

25 views

### Proving first order logic in coq

I want to prove something like: Theorem new_theorem : $\forall (A B: \text{Prop}), ((A \wedge B) \iff (B \wedge A))$. in coq. I know, i could just type firstorder., but could i prove this in coq ...
87 views

### Curious tautological pattern on“p->p”

I found something that boggles me ( I'm really a beginner in symbolic logic, so maybe it's very trivial). I was practicing with truth-tables, and I found that: "p->p" is a tautology "(p->p)->p" is ...
29 views

### With the use of resolution method decide whether this is correct. If not, provide a counter example [closed]

I am learning Logic and solving to decide if the stated formula is correct by using the resolution method. {(¬p ∨ q), (p → r)} |= r ∨ q . Below is my unsure attempt to the question. All corrections ...
50 views

### Decide whether this is correct, using the method of resolution. If not, provide a counter example.

I am new to logic and wanted to decide whether the following is correct using the method of resolution: |= p → ¬ (p → (p ∧ (p ∨ q))) My attempt to this I answered that the conclusion is incorrect, ...
42 views

### Transforming Hilbert-style Axiom Systems for Classical Propositional Logic and Retaining Soundness and Completeness

First off, I will use ~ for negation, & for conjunction, V for disjunction, -> for implication, and <-> for bi-conditional. To the question: The axioms of classical propositional logic (CPL) ...
72 views

### Meta-logic of Hilbert-style propositional calculus

I am trying to study the foundations of mathematics from the bottom-up (propositional logic then predicate logic then the axioms of set theory.) Currently, I'm considering the following Hilbert-style ...
48 views

### Quantifiers and empty set

Let $X$ and $Y$ be sets. Suposse that $X=\varnothing$ and $Y\neq \varnothing$. Is $$(\forall x\in X) (\exists y\in Y)\;p(x,y)$$ TRUE?
16 views

### Simplifying propositional logic formulas [closed]

I'm learning propositional logic, but simplifying the formulas are difficult for me... I have $P\vee Q \implies Q\wedge\neg P$. Here i am not quite sure how i should approach this. I started solving ...
85 views

24 views

42 views

### Derivation of $\text{A} \vee \neg{\text{A}}$ without a premise.

In one of my homework problems, I need to deduce that $\text{A} \vee \neg{\text{A}}$ without a premise. The lecturer mentioned that students should "combine" answers for the previous two problems ...
83 views

### Logically, deductively, tautologically, semantically, syntactically valid arguments, what is the difference?

I've read 4 logic books in total but i'm getting crazy with all these xxxally valid argument what is the difference?? What is the difference between Logically, deductively, tautologically, ...
24 views

### finding CNF and a logically Logically equivalent DNF for Propositional form (p→(q→r)) [closed]

I can write the truth table for (p→(q→r)) but i was not able to find the required CNF and a logically Logically equivalent DNF for Propositional form (p→(q→r)) . It's confusing.
19 views

### Trichotomy and Xor - odd results

I've come across something odd. If one wants to logically formulate trichotomy the following formulation is incorrect: $$(\alpha \oplus \beta) \oplus \gamma$$ For all WFF's being $T$ one gets that ...
40 views

### Question about MU puzzle from GEB

In MU puzzle: https://en.wikipedia.org/wiki/MU_puzzle#The_puzzle, We have "MU" string and 4 rules. Now when compared this to logic the wiki article says "The MI string is akin to a single axiom, and ...
27 views

### Propositional and First Order Logic Tool to analyse formula

I am looking for an online tool which analyses a given propositional and/or first order logic formula. For example the tool should output, whether the given formula is satisfiable, its rank, ... If ...
33 views

### I found that resolution is not complete: what do I miss?

I am a newbie in propositional logic and I am learning by myself. I am reading the book A First Course in Logic : An Introduction to Model Theory, Proof Theory, Computability, and Complexity by Hedman....