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)

1
vote
1answer
46 views

Show that any consistent extension $L^*$ of L has a consistent extension ${{L^*}^*}$ which is complete.

If $L^*$ is a consistent extension of L and $\phi$ is a formula which is not a theorem of $L^*$ , then the extension of $L^*$ obtained by including $(¬\phi)$ as an extra axiom is consistent. Show ...
1
vote
1answer
59 views

Mathematical Logic Past Paper Question: n is a positive integer, $X_n$ = ${(x_1,.,x_n) : x_i ∈ {T,F}}$ is the set of n- tuples from {T,F}.

Suppose $n$ is a positive integer and $X_n = \{(x_1,\ldots ,x_n) \colon x_i ∈ \{T,F\}\}$ is the set of $n$- tuples from $\{T,F\}$. Suppose $f\colon X_n \to \{T,F\}$ is a function and $f(x) = T$ for ...
2
votes
4answers
58 views

Hilbert System with propositional logic $p \rightarrow q,\neg q \vdash \neg p$

This is my set of axiom $A \rightarrow (B\rightarrow A)$ $(A\rightarrow(B\rightarrow C))\rightarrow ((A\rightarrow B) \rightarrow (A \rightarrow C))$ $(\neg A \rightarrow B)\rightarrow ((\neg A ...
0
votes
1answer
48 views

Hilbert proof systems with hypothesis

This is my set of axioms: $A \rightarrow (B\rightarrow A)$ $(A\rightarrow(B\rightarrow C))\rightarrow ((A\rightarrow B) \rightarrow (A \rightarrow C))$ $(\neg A \rightarrow B)\rightarrow ((\neg A ...
4
votes
4answers
76 views

Find propositional formulas $\phi$ and $\psi$ such that $(\phi \rightarrow (\psi \rightarrow (¬\psi)))$ is a theorem of L.

Find propositional formulas $\phi$ and $\psi$ such that $(\phi \rightarrow (\psi \rightarrow (¬\psi)))$ is a theorem of L. So every axiom is a theorem of L so I thought there would be some way to ...
1
vote
0answers
18 views

Propositonal equivalence and compound proposition

Without using truth tables, show that the statements ‘If you did all problems in the book, attended all lectures and completed all assignments, then you will get an A in Discrete Math’ and ...
1
vote
1answer
91 views

Mathematical logic

Given: $[(A \lor B) \land (A \lor C)] \rightarrow [A \lor (B \land C)]$; $\lnot((x_1 < x_2) \rightarrow (x_1 \cdot x_3 > x_2 \cdot x_3))$ $\forall x_2:f_1^2(x_2, x_3) \rightarrow ...
0
votes
1answer
37 views

Do Hypothetical Syllogism and Contraction Come as Sufficient for Self-Distribution?

If we have the following axioms (under detachment) 1. CCpqCCqrCpr-hypothetical syllogism 2. CCpCpqCpq-contraction 3. CpCqp-recursive variable prefixing Then ...
3
votes
2answers
111 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 ...
1
vote
1answer
34 views

Show that there exists a satisfactory assignment for the unstandard language of arithmetic $\{\textbf{0}, ', <_1\}$

Consider: $A1: \textbf{0} \not = x'$ $A2: x'=y' \rightarrow x = y$ $A3: \neg x < \textbf{0}$ $A4: x < y' \leftrightarrow (x < y \vee x = y)$ $A5: \textbf{0} < y ...
2
votes
2answers
67 views

What does it mean for a set of sentences $\mathcal{T}$ to “secure” a set of sentences $\Delta$?

I know the standard interpretation is: $\mathcal{T}$ secures $\Delta$ iff every interpretation that makes all members of $\mathcal{T}$ true makes at least one member of $\Delta$ true. ...
0
votes
1answer
32 views

2 Distinct Bijective functions

I have that A is a set of $2k^2$ so it equals $\{2,8,18,32,50...\}$ How do you Construct two distinct bijections $f, g : \mathbb{Z}^{+} \to A$. I was able to get $f(x)=2x^2$ what would $g(x)$ be? ...
1
vote
2answers
68 views

Construct the truth table?

Any body help me .. How to solve this? (i) $(p\land q)\to (p \leftrightarrow (q \lor r))$ (ii) $(p \leftrightarrow q) \leftrightarrow ((p\land q) \lor (\neg q \land \neg p))$ (iii) ...
2
votes
2answers
94 views

How to write negation of statements?

How to write negation of following statements in words? ...
2
votes
3answers
62 views

Construct XNOR with only OR gates

Is it possible to construct the XNOR gate which is given as, a XNOR b = (a AND b) OR (~a AND ~b), by using only OR gates. So from the definition, the question boils down to: can you construct the AND ...
3
votes
1answer
366 views

Using a truth table to determine if valid or invalid

I have some questions like if $P$ then $Q, P$ therefor $Q$ for example, how can you tell from writing your truth table if therefor $Q$ is valid or invalid? I mean I know its true because Modus Ponens ...
0
votes
2answers
44 views

Definition nested and unnested first order formulas

What's the definition of nested and unnested formulas in a first order language? I came across the term in a model theory book i'm reading, and I can't seem to find it defined there, or in my brief ...
2
votes
1answer
66 views

Proving the propositional tableau sound and complete

There is something fundamental that stops me from understanding the proofs for the propositional tableau. (1) soundness proves that all theorems that can be proved are valid (2) completeness proves ...
0
votes
1answer
35 views

How's my proof?

Prove that not every boolean function is equal to a boolean function constructed by only using $∧$ and $∨$. If p,q = (0,1) (p$∧$q)$∨$q = (0$∧$1)$∨$1 = 1 (p$∧$q)$∨$~q = (0$∧$1)$∨$~1 = 0 Therefore ...
3
votes
1answer
76 views

Prove if Tautology, Contradicton, or Neither. Is my proof ok?

Determine whether $((p \Rightarrow q) \Rightarrow r) \Leftrightarrow (p \Rightarrow (q \Rightarrow r))$ is a tautology, a contradiction, or neither. If $p,q,r = (0,0,0)$ then $((p \Rightarrow ...
0
votes
1answer
63 views

Unique Readability Theorem proof

I really do not understand the Unique Readability Theorem proof (in Enderton's book). The proof essentially goes that we have wffs $\alpha, \beta, \gamma, \delta$, and that if we assume $(\alpha ...
0
votes
1answer
29 views

Proving ∀x (0|x ↔ x = 0) (divisor by Zero) - Euclidean Algorithm

I am trying to proof the total correction of Euclidean Algorithm, so I am up to proof one of the following properties which is divisor by Zero. Given this Axiom: ...
1
vote
1answer
49 views

Proof by induction of propositional formulas

I have two inductively defined operations: $\text{bin}$ base case: If $p$ is a propositional letter, then $\text{bin}(p) = 0$ inductive step $\text{bin}(\neg \phi) = \text{bin} (\phi)$ ...
5
votes
2answers
93 views

Is there a logical interpretation for equalizer and co-equalizer?

I know the logical equivalent to several universal constructions. For example product $\times$ is $\land$ and co-product $+$ is $\lor$. The associated arrows are projection and inclusion. The ...
-1
votes
2answers
70 views
4
votes
1answer
140 views

What are those “things that cannot be proved using only ordinary rules of inference”?

The online edition of the book Introduction to Logic by Michael Genesereth and Eric Kao, has a detail that left me confused. CHAPTER 4 [...] 4.2 Linear Proofs [...] The ...
0
votes
1answer
87 views

Can you conclude that A = B if A, B, and C are sets such that…

a. A ∪ C = B ∪ C b. A ∩ C = B ∩ C c. A ∩ C = B ∩ C and A ∪ C = B ∪ C My method of solving this was to convert everything to propositional logic, then to solve it to show that none of the above are ...
1
vote
5answers
69 views

If one of the hypotheses holds, then one of the conclusions holds. (looking for a proof)

Using a huge truth table, I proved the theorem below. I cannot find a more elegant proof. I tried to rewrite expressions; e.g. using the distributive laws and the laws of absorption - to no avail. Is ...
0
votes
2answers
119 views

How can I prove [P->(Q->R)] is equivalent to [(P^Q) ->R]

I'm a freshman CS student at my university and i'm struggling with understanding my professor through his thick accent. I've asked him to explain the proof for this multiple times and still have ...
2
votes
2answers
100 views

Prove P∧(Q∨R)→(P∧Q)∨(P∧R) from P∧(Q∨R) using Natural Deduction

I am trying to prove P∧(Q∨R)→(P∧Q)∨(P∧R) from P∧(Q∨R) using Natural Deduction. Here is my attempt using JAPE application. ...
0
votes
1answer
64 views

A finite set of wffs has an independent equivalent subset

This seems to be a common exercise among many books (cf. Enderton, p. 28, van Dalen, p. 45, Hinman, p. 51, Chang and Keisler, p. 18), with some minor variations among them. The idea is simple. Say ...
2
votes
1answer
43 views

If $\phi$ is satisfiable and $\mathscr{S}$ is countable, then the set of all models of $\phi$ has the cardinality of the continuum

I have just started reading Chang and Keisler and I'm already stuck in an exercise. Let $\mathscr{S}$ be a countable set of sentence letters (i.e. $\mathscr{S} = \{S_0, S_1, S_2, \dots\}$ or some ...
11
votes
1answer
928 views

Minimum number of different clues in a Sudoku

I wonder if there are proper $9\times9$ Sudokus having $7$ or less different clues. I know that $17$ is the minimum number of clues. In most Sudokus there are $1$ to $4$ clues of every number. ...
3
votes
2answers
118 views
1
vote
3answers
66 views

Disjunctive simplification

What is this rule of inference called? $(P\wedge Q)\vee(P\wedge\neg Q)\vdash P$ My (silly) motivation is this answer.
1
vote
2answers
135 views

How to determine whether a set of propositions is consistent?

Definition of consistency is: A set of formulas ⊆ WFF is consistent iff there is no A ∈ WFF such that Σ ⊢ A and Σ ⊢ (¬A). Say you have a set of propositions statements (i.e. $A \lor B \rightarrow C$, ...
0
votes
2answers
64 views

Convert this solution to inference notation

This is a proof for De Morgan's Law. Could you help me convert this to inference notation so I can understand the proof better? I find it hard reading this, specifically, which line each assumption ...
2
votes
1answer
51 views

Simple Propositional Logic Explaination?

In this example, the prof states that "Q->R doesn't depend on the assumption Q so he can discharge it, but without assumption Q, he couldn't have concluded with Q->R so the answer still depends on the ...
1
vote
2answers
80 views

Use of propositional logic connectives in the meta-language

I have a doubt that might seem a bit confusing so i will try to explain it the clearer i can. Suppose we have an expression "A o B" in the meta-language, where 'o' refers to those logical ...
1
vote
1answer
100 views

Answering questions with truth tables

"With every dinner I have three rules": If I don't drink wine, then I eat soup If I eat soup and drink wine, then I'll have some pudding If I have pudding or don't drink wine, then I'll skip the ...
2
votes
1answer
83 views

Trouble understanding Lindenbaum's lemma's proof

I'm stuck on the section (b) of the proof of the Lindenbaum's lemma in Geoffrey Hunter's Metalogic (part 32.12). Can't these two derivations ($\Gamma ' \vdash_{PS} A $ and $\Gamma ' \vdash _{PS}\sim A ...
2
votes
1answer
49 views

Help solving a challenge - relational algebra or second order logic

I am a self-taught man and I'm posting my first question here. I'm facing a challenge I'd like to solve. Based on what I know it fits propositional calculus (hope it is). Suppose 3 people: a ...
1
vote
1answer
25 views

semantic equivalence

Hi I am looking to prove that this equivalence holds using rules of semantic equivalence, or if it does not hold give an interpretation that shows it. (p⇒q)∨(r⇒q)≡p⇒(r⇒q) I get ≡implication ...
1
vote
2answers
54 views

prove formulae using natural deduction

Hello I am trying to prove this: ⊢p⇒p∧(p∨q) using natural deduction. p ⊢ p∧(p∨q) p, assumption p ⊢ (p∨q) p, assumption but dont seem to be getting anywhere. can someone please help? thank you. ...
1
vote
1answer
49 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
5answers
210 views

truth tables and validity of arguments

$ p $ $ p \to q $ $ \lnot q \lor r$ $ \therefore r$ In order to prove validity with truth tables, do 1) 2) and 3) have to be true in order for the conclusion to be true?
1
vote
1answer
29 views

Is my answer correct for this Logical Analysis of Arguments?

The question is: If U is a subspace of V, then U is a subset of V, U contains the zero vector, and U is closed under addition. U is a subset of V, and if U is closed under addition then U contains ...
1
vote
2answers
24 views

question about equivalence of boolean statements

Does the function $(p \land q) \lor r$ equal the function $p \land (q \lor r)$? please it would be suitable if in your feedback you will include which algebraic rule for boolean function to follow.. ...
6
votes
5answers
197 views

The deep structure of logical formulas

A long-standing question to which I never found a concise answer is: Is there something like an unambiguous deep structure of a formula of propositional logic, opposed to its comparingly ...
0
votes
1answer
109 views

Propositional calculus proof must involve instance of $(\neg \neg p \Rightarrow p )$

Hi this is a question about propositional calculus. The axioms I am working with are: $(p \Rightarrow (q\Rightarrow p))$ $ ((p \Rightarrow (q \Rightarrow r)) \Rightarrow ((p \Rightarrow q ) ...