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

5,467 questions
Filter by
Sorted by
Tagged with
26 views

### propsitional logic exersice

Show that [(p ∨ q) ∧ (r ∨ ¬q)] → (p ∨ r)] is a tautology by making a truth table, and then again by using an argument that considers the two cases “q is true” and “q is false” I need help on this one ....
1 vote
31 views

### Uniform continuity and the order of quantifiers

I’m taking my first course in real analysis, and I’m trying to prove the following proposition. Proposition: If $f:S\to\mathbb{R}$ is uniformly continuous, then $f$ is continuous. In comparing ...
126 views

### Open source program that generate "random" theorems by exploration

With some formal systems, it's possible to enumerate all the theorems. This is the case for instance in propositional calculus or in some first-order theories with a recursively enumerable set of ...
1 vote
51 views

### Can this disjunction be eliminated?

This is a question about classical propositional logic. Definitions: If there is a proof from $\alpha$ to $\beta$, we'll write $\alpha \vdash \beta$. We'll say that $\alpha$ is equivalent to $\beta$ ...
1 vote
99 views

1 vote
55 views

63 views

61 views

### Is this natural deduction proof of $\exists x \neg Px \vdash \neg \forall x Px$ correct?

When it comes to proofs there is no way to tell whether I have done correct or not. In the solution they did in another way which makes me wonder if this correct? For future question, how can I verify ...
48 views

### Propositional Logic: ¬p → ¬q, q V ¬r ⊢ r → p

Is this proof correct? ¬p → ¬q, q V ¬r ⊢ r → p ...
982 views

### What exactly does $X - (Y ∪ Z)$ mean?

Does the above mean: $x$ is in $X$ but [$x$ is not in $Y$ or $x$ is not in $Z$] OR $x$ is in $X$ but [$x$ is not in $Y$ and $x$ is not in $Z$] ?
1 vote
38 views

### Provide an interpretation where a formula $\forall x \exists y G(x,y) \wedge \neg \exists z G(z,z)$ of predicate logic holds true

Provide an interpretation where $∀_{x}∃_{y}G(x,y) ∧ ¬∃_{z}G(z,z)$ holds. G(x, y) = x "greater than" y This gives us the meaning that for all numbers, there exists a number where x is ...
1 vote
88 views

### Is this natural deduction proof of $\exists x Fx \to G \vdash \forall x [Fx \to G]$ in predicate logic correct?

Like the title says, is this correct? Edit I left out a big detail: G is a closed formula (meaning it does not contain x as a free variable).
1 vote
40 views

### Did I do this propositional logic proof correctly?

This is how I have tried to solve it but I have no answer sheet to check whether I did correct or not.Is this correct? $q→r, p ⊢ (p→q)→(r∧q)$
65 views

### How to use predicate logic to write "Product of an even number and another number is even"?

So this is the correct solution where $U(x)$ means "odd" but personally I only did it with one of them , as in , I didn't use the or-statement to show "when either $y$ is even or $z$ is ...
172 views

### Seeking a More Efficient Solution for Knights and Knaves Logic Puzzle

I am working on a Knights and Knaves logic puzzle, and I have formulated a solution using a truth table. However, I'm wondering if there's a more efficient or faster way to arrive at the solution ...
91 views

### Prove that every tautology of the form (α → β) can be broken into (α → γ) and (γ → β), where the variables in γ aren’t in exactly one of α and β

Given a tautology of the form (α → β), where α and β are propositions, I want to prove that there exists another proposition γ such that (α → γ) and (γ → β) are both tautologies, and that γ can only ...
129 views

### How to prove with natural deduction?

Given this question, I tried solving in the first picture as you can see, but I didn't know how to continue and the second image is the right way to solve it. My question is have I done right so far? ...