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

3,630 questions
Filter by
Sorted by
Tagged with
1answer
26 views

### Precedence between implication and bi-implication

I came across this question: Let p, q, and r be the propositions ...
1answer
24 views

### How to determine if given function is functionally complete

Given any random boolean function, is their any step wise procedure to find out whether it is functionally complete? The simplest approach I came across is this: We need to find whether given ...
1answer
34 views

### 𝛾-rule in semantic tableaux of first-order logic

I'm a novice and I'm trying to understand semantic tableaux in First-Order Logic. 𝛿 - existential rule makes sense to me, if ∃x A(x) is true, saying "let c by ...
2answers
33 views

### Problem with formulating the negation of a statement

The excersise asks us to prove with an Indirect Proof that if $abc$ is an irrational number then at most two of $a,b,c$ are rational numbers. So we have, Let $P$ denote "$abc$ is irrational" and let ...
2answers
37 views

### First Order Logic: Diffrence b/w $\{\forall x P(x) \implies Q(x) \}$ and $\{ (\forall x P(x)) \implies Q(x)) \}$

There is GATE exam question which is confusing (in first look at least to solve): Which of the following first order formula is logically valid? Here $\alpha(x)$ is a first order formula with ...
1answer
40 views

### Interpretation of a valuation function when we have a known truth and an assumed truth in a proof

To provide context, I am currently learning about Conditional Introduction. This is the first time in this propositional calculus unit that I have encountered an assumed truth ; previously, all ...
1answer
45 views

1answer
45 views

### Reference for normalization of propositional logic natural deduction.

I'm looking for a reference for the normalization of classical propositional logic natural deduction. I have heard that D.Prawitz's book Natural Deduction is a good reference on the FOL. But first I ...
0answers
35 views

### Expression deduction algorithm in propositional logic

I need to find a way to deduce an expression in propositional logic. The given expression $\alpha$ contains up to $3$ variables. I need to find a list of hypotheses $\Gamma$ consisting only of ...
1answer
40 views

### Is the set of Valuation Functions finite?

I've been learning about interpretation functions and valuation functions. Intuitively, it seems as though there are an infinite number of Interpretation Functions, which I will denote as $I_n$. i.e....
2answers
66 views

### Natural deduction proof of $p \lor (p\implies q)$ with propositional calculus [closed]

I'm having a bit of trouble proving this with the propositional calculus rules. $$p \lor (p\implies q)$$ Would someone mind helping me and showing which rules they've used with an explanation! Thanks!...
2answers
72 views

### How to prove the distributive law for propositional logic without using truth tables or natural deduction.

I haven't learnt natural deduction yet so I'm completely stuck on how to proceed. One tip I was given was to use the properties of negation but again, that's not really helping.
1answer
72 views

### First-Order Logic: Formalisation of the phrase “Not all that glitters is gold”

I am trying to determine which of the following expressions are a valid formalisation of the phrase "Not all that glitters is gold". I have the following options: (1) ∃x. (𝖦𝗅𝗂𝗍𝗍𝖾𝗋(x)→𝖦𝗈𝗅𝖽(...
0answers
23 views

0answers
28 views

### How can I simplify this proposition where 4 out of 5 values are true and the remaining 1 out of 5 is false?

I am fairly new to logic and I am curious as to whether it is possible to simplify this proposition where 4 out of 5 values must be true and one of them has to be false. (P1 ∧ P2 ∧ P3 ∧ P4 ∧ ¬P5) ∨ (...
1answer
76 views

### How to formalize this simple problem in logic?

I want to translate this problem with a simple logical expression. Say that my system only accepts tuples of strings $(s=s_1...s_n$, $t=t_1...t_n)$ where $s_i$ and $t_i \in \{0, 1, 2\}$, that are ...
4answers
40 views

### Prove that $(\neg P \lor Q)\wedge (P \lor \neg R)\wedge (\neg P \lor \neg Q)$ and $\neg (P \lor R)$ logically equivalent.

Q. Prove that $(\neg P \lor Q)\wedge (P \lor \neg R)\wedge (\neg P \lor \neg Q)$ and $\neg (P \lor R)$ logically equivalent. I can get a feel for why this will be true. My argument goes as follows: ...
2answers
58 views

1answer
15 views

### Absorption's Law - Negative proposition affects the law?

This is a simple question. It's known that the absorption's law is like the following example: p ∧ (p V q) = p But, if the proposition has a negation, does this affect the law? for example: p ∧...