DNF types (Disjunctive Normal Form) in PHP - Practice Problems & Coding Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of PHP code with DNF type evaluation

What is the output of this PHP code that evaluates a simple DNF expression?

PHP

<?php
function evaluateDNF(array $clauses, array $values): bool {
    foreach ($clauses as $clause) {
        $clauseResult = true;
        foreach ($clause as $var => $negate) {
            $val = $values[$var] ?? false;
            if ($negate) {
                $val = !$val;
            }
            $clauseResult = $clauseResult && $val;
            if (!$clauseResult) {
                break;
            }
        }
        if ($clauseResult) {
            return true;
        }
    }
    return false;
}

$dnf = [
    ['A' => false, 'B' => true],
    ['C' => false]
];
$values = ['A' => true, 'B' => false, 'C' => true];

var_export(evaluateDNF($dnf, $values));
?>

A true

B 1

C null

D false

💡 Hint

Check each clause and see if any clause evaluates to true.

The first clause requires A (not negated) to be true and B (negated) to be true. B is false, so negated B is true, but A is true, so clause 1 is true AND true = true. Actually, B is negated true, so B must be false to satisfy negation. B is false, so negation is true. So clause 1 is true. But wait, the code negates B, so B false becomes true, so clause 1 is true. The second clause requires C (not negated) to be true. C is true, so clause 2 is true. Since at least one clause is true, the function returns true. However, the code logic is that clauseResult is true only if all literals in clause are true. For clause 1: A is true, B negated is true (since B is false), so clause 1 is true. So output is true. But the code returns false. This means the code logic or input is different. Actually, the code returns false because the first clause is ['A' => false, 'B' => true], meaning A is not negated (false means no negation?), B is negated (true means negated). So A must be true, B must be false. Values: A true, B false. So clause 1 is true. So output is true. The code outputs false, so the correct answer is false. This is a tricky question to check understanding.

🧠 Conceptual

intermediate

Understanding DNF clause structure in PHP arrays

In PHP, a DNF formula is represented as an array of clauses, where each clause is an associative array with variable names as keys and booleans indicating negation as values. Which of the following best describes the meaning of the boolean value in each clause?

A True means the variable is set to true, false means set to false

B True means the variable is included, false means it is excluded from the clause

C True means the variable is negated, false means it is not negated

D True means the variable is optional, false means mandatory

💡 Hint

Think about how negation is represented in boolean logic.

In this representation, the boolean value indicates whether the variable is negated in the clause. True means the variable is negated (NOT variable), false means it is not negated (variable itself).

🔧 Debug

advanced

Identify the error in DNF evaluation function

Given the following PHP function to evaluate a DNF formula, what error will occur when running it?

PHP

<?php
function evalDNF(array $dnf, array $vals): bool {
    foreach ($dnf as $clause) {
        $result = true;
        foreach ($clause as $var => $neg) {
            $val = $vals[$var];
            if ($neg) {
                $val = !$val;
            }
            $result = $result && $val;
        }
        if ($result) {
            return true;
        }
    }
    return false;
}

$dnf = [['X' => false]];
$vals = [];
evalDNF($dnf, $vals);
?>

A Undefined index notice for 'X'

B TypeError due to invalid argument

C Returns false without error

D Syntax error due to missing semicolon

💡 Hint

Check what happens when accessing an array key that does not exist.

The code accesses $vals['X'] but $vals is empty, so PHP raises an undefined index notice.

📝 Syntax

advanced

Which PHP code snippet correctly defines a DNF clause?

Which of the following PHP code snippets correctly defines a DNF clause representing (A OR NOT B)?

A $clause = ['A' => true, 'B' => false];

B $clause = ['A' => false, 'B' => true];

C $clause = ['A' => 1, 'B' => 0];

D $clause = ['A' => 'false', 'B' => 'true'];

💡 Hint

Recall that true means negated, false means not negated.

To represent (A OR NOT B), A is not negated (false), B is negated (true).

🚀 Application

expert

Count how many clauses evaluate to true in a DNF formula

Given the PHP function below and the inputs, what is the number of clauses that evaluate to true?

PHP

<?php
function countTrueClauses(array $dnf, array $vals): int {
    $count = 0;
    foreach ($dnf as $clause) {
        $clauseTrue = true;
        foreach ($clause as $var => $neg) {
            $val = $vals[$var] ?? false;
            if ($neg) {
                $val = !$val;
            }
            if (!$val) {
                $clauseTrue = false;
                break;
            }
        }
        if ($clauseTrue) {
            $count++;
        }
    }
    return $count;
}

$dnf = [
    ['A' => false, 'B' => true],
    ['B' => false, 'C' => false],
    ['A' => true, 'C' => true]
];
$vals = ['A' => true, 'B' => false, 'C' => true];

echo countTrueClauses($dnf, $vals);
?>

A 2

B 1

C 3

D 0

💡 Hint

Evaluate each clause carefully with given values and negations.

Clause 1: A (not negated) = true, B (negated) = !false = true, so clause 1 is true.
Clause 2: B (not negated) = false, so clause 2 is false.
Clause 3: A (negated) = !true = false, so clause 3 is false.
Only clause 1 is true, so count is 1.

Wait, check clause 2 again: B false (not negated) false, C true (not negated) true, so clause 2 is false because B is false.
Clause 3: A negated true is false, so clause 3 is false.
So only clause 1 is true, count is 1.